1// Copyright 2014 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5/** 6 * @fileoverview A semantic tree for MathML expressions. 7 * 8 * This file contains functionality to compute a semantic interpretation from a 9 * given MathML expression. This is a very heuristic approach that assumes a 10 * fairly simple default semantic which is suitable for K-12 and simple UG 11 * mathematics. 12 * 13 */ 14 15goog.provide('cvox.SemanticTree'); 16goog.provide('cvox.SemanticTree.Node'); 17 18goog.require('cvox.DomUtil'); 19goog.require('cvox.SemanticAttr'); 20goog.require('cvox.SemanticUtil'); 21 22 23/** 24 * Create an initial semantic tree. 25 * @param {!Element} mml The original MathML node. 26 * @constructor 27 */ 28cvox.SemanticTree = function(mml) { 29 /** ID counter. 30 * @type {number} 31 * @private 32 */ 33 this.idCounter_ = 0; 34 35 /** Original MathML tree. 36 * @type {Node} 37 */ 38 this.mathml = mml; 39 40 /** @type {cvox.SemanticTree.Node} */ 41 this.root = this.parseMathml_(mml); 42}; 43 44 45/** 46 * @param {number} id Node id. 47 * @constructor 48 */ 49cvox.SemanticTree.Node = function(id) { 50 /** @type {number} */ 51 this.id = id; 52 53 /** @type {Array.<Element>} */ 54 this.mathml = []; 55 56 /** @type {cvox.SemanticTree.Node} */ 57 this.parent = null; 58 59 /** @type {cvox.SemanticAttr.Type} */ 60 this.type = cvox.SemanticAttr.Type.UNKNOWN; 61 62 /** @type {cvox.SemanticAttr.Role} */ 63 this.role = cvox.SemanticAttr.Role.UNKNOWN; 64 65 /** @type {cvox.SemanticAttr.Font} */ 66 this.font = cvox.SemanticAttr.Font.UNKNOWN; 67 68 /** @type {!Array.<cvox.SemanticTree.Node>} */ 69 this.childNodes = []; 70 71 /** @type {string} */ 72 this.textContent = ''; 73 74 /** Branch nodes can store additional nodes that can be useful. 75 * E.g. a node of type FENCED can have the opening and closing fences here. 76 * @type {!Array.<cvox.SemanticTree.Node>} 77 */ 78 this.contentNodes = []; 79}; 80 81 82/** 83 * Retrieve all subnodes (including the node itself) that satisfy a given 84 * predicate. 85 * @param {function(cvox.SemanticTree.Node): boolean} pred The predicate. 86 * @return {!Array.<cvox.SemanticTree.Node>} The nodes in the tree for which the 87 * predicate holds. 88 */ 89cvox.SemanticTree.Node.prototype.querySelectorAll = function(pred) { 90 var result = []; 91 for (var i = 0, child; child = this.childNodes[i]; i++) { 92 result = result.concat(child.querySelectorAll(pred)); 93 } 94 if (pred(this)) { 95 result.unshift(this); 96 } 97 return result; 98}; 99 100 101 /** 102 * Returns an XML representation of the tree. 103 * @param {boolean=} brief If set attributes are omitted. 104 * @return {Node} The XML representation of the tree. 105 */ 106 cvox.SemanticTree.prototype.xml = function(brief) { 107 var dp = new DOMParser(); 108 var xml = dp.parseFromString('<stree></stree>', 'text/xml'); 109 110 var xmlRoot = this.root.xml(xml, brief); 111 xml.childNodes[0].appendChild(xmlRoot); 112 113 return xml.childNodes[0]; 114 }; 115 116 117 /** 118 * An XML tree representation of the current node. 119 * @param {Document} xml The XML document. 120 * @param {boolean=} brief If set attributes are omitted. 121 * @return {Node} The XML representation of the node. 122 */ 123 cvox.SemanticTree.Node.prototype.xml = function(xml, brief) { 124 /** 125 * Translates a list of nodes into XML representation. 126 * @param {string} tag Name of the enclosing tag. 127 * @param {!Array.<!cvox.SemanticTree.Node>} nodes A list of nodes. 128 * @return {Node} An XML representation of the node list. 129 */ 130 var xmlNodeList = function(tag, nodes) { 131 var xmlNodes = nodes.map(function(x) {return x.xml(xml, brief);}); 132 var tagNode = xml.createElement(tag); 133 for (var i = 0, child; child = xmlNodes[i]; i++) { 134 tagNode.appendChild(child); 135 } 136 return tagNode; 137 }; 138 var node = xml.createElement(this.type); 139 if (!brief) { 140 this.xmlAttributes_(node); 141 } 142 node.textContent = this.textContent; 143 if (this.contentNodes.length > 0) { 144 node.appendChild(xmlNodeList('content', this.contentNodes)); 145 } 146 if (this.childNodes.length > 0) { 147 node.appendChild(xmlNodeList('children', this.childNodes)); 148 } 149 return node; 150 }; 151 152 153/** 154 * Serializes the XML representation of the tree. 155 * @param {boolean=} brief If set attributes are omitted. 156 * @return {string} Serialized string. 157 */ 158cvox.SemanticTree.prototype.toString = function(brief) { 159 var xmls = new XMLSerializer(); 160 return xmls.serializeToString(this.xml(brief)); 161}; 162 163 164/** 165 * Pretty print the XML representation of the tree. 166 * @param {boolean=} brief If set attributes are omitted. 167 * @return {string} The formatted string. 168 */ 169cvox.SemanticTree.prototype.formatXml = function(brief) { 170 var xml = this.toString(brief); 171 return cvox.SemanticTree.formatXml(xml); 172}; 173 174 175/** 176 * Pretty prints an XML representation. 177 * @param {string} xml The serialised XML string. 178 * @return {string} The formatted string. 179 */ 180cvox.SemanticTree.formatXml = function(xml) { 181 var reg = /(>)(<)(\/*)/g; 182 xml = xml.replace(reg, '$1\r\n$2$3'); 183 reg = /(>)(.+)(<c)/g; 184 xml = xml.replace(reg, '$1\r\n$2\r\n$3'); 185 var formatted = ''; 186 var padding = ''; 187 xml.split('\r\n') 188 .forEach(function(node) { 189 if (node.match(/.+<\/\w[^>]*>$/)) { 190 // Node with content. 191 formatted += padding + node + '\r\n'; 192 } else if (node.match(/^<\/\w/)) { 193 if (padding) { 194 // Closing tag 195 padding = padding.slice(2); 196 formatted += padding + node + '\r\n'; 197 } 198 } else if (node.match(/^<\w[^>]*[^\/]>.*$/)) { 199 // Opening tag 200 formatted += padding + node + '\r\n'; 201 padding += ' '; 202 } else { 203 // Empty tag 204 formatted += padding + node + '\r\n'; 205 } 206 }); 207 return formatted; 208}; 209 210 211/** 212 * Serializes the XML representation of a node. 213 * @param {boolean=} brief If attributes are to be omitted. 214 * @return {string} Serialized string. 215 */ 216cvox.SemanticTree.Node.prototype.toString = function(brief) { 217 var xmls = new XMLSerializer(); 218 var dp = new DOMParser(); 219 var xml = dp.parseFromString('', 'text/xml'); 220 return xmls.serializeToString(this.xml(xml, brief)); 221}; 222 223 224/** 225 * Adds attributes to the XML representation of the current node. 226 * @param {Node} node The XML node. 227 * @private 228 */ 229cvox.SemanticTree.Node.prototype.xmlAttributes_ = function(node) { 230 node.setAttribute('role', this.role); 231 if (this.font != cvox.SemanticAttr.Font.UNKNOWN) { 232 node.setAttribute('font', this.font); 233 } 234 node.setAttribute('id', this.id); 235}; 236 237 238/** Creates a new node object. 239 * @return {cvox.SemanticTree.Node} The newly created node. 240 * @private 241 */ 242cvox.SemanticTree.prototype.createNode_ = function() { 243 return new cvox.SemanticTree.Node(this.idCounter_++); 244}; 245 246 247/** 248 * Replaces a node in the tree. Updates the root node if necessary. 249 * @param {!cvox.SemanticTree.Node} oldNode The node to be replaced. 250 * @param {!cvox.SemanticTree.Node} newNode The new node. 251 * @private 252 */ 253cvox.SemanticTree.prototype.replaceNode_ = function(oldNode, newNode) { 254 var parent = oldNode.parent; 255 if (!parent) { 256 this.root = newNode; 257 return; 258 } 259 parent.replaceChild_(oldNode, newNode); 260}; 261 262 263/** 264 * Updates the content of the node thereby possibly changing type and role. 265 * @param {string} content The new content string. 266 * @private 267 */ 268cvox.SemanticTree.Node.prototype.updateContent_ = function(content) { 269 // Remove superfluous whitespace! 270 content = content.trim(); 271 if (this.textContent == content) { 272 return; 273 } 274 var meaning = cvox.SemanticAttr.lookupMeaning(content); 275 this.textContent = content; 276 this.role = meaning.role; 277 this.type = meaning.type; 278 this.font = meaning.font; 279}; 280 281 282/** 283 * Adds MathML nodes to the node's store of MathML nodes if necessary only, as 284 * we can not necessarily assume that the MathML of the content nodes and 285 * children are all disjoint. 286 * @param {Array.<Node>} mmlNodes List of MathML nodes. 287 * @private 288 */ 289cvox.SemanticTree.Node.prototype.addMathmlNodes_ = function(mmlNodes) { 290 for (var i = 0, mml; mml = mmlNodes[i]; i++) { 291 if (this.mathml.indexOf(mml) == -1) { 292 this.mathml.push(mml); 293 } 294 } 295}; 296 297 298/** 299 * Removes MathML nodes from the node's store of MathML nodes. 300 * @param {Array.<Node>} mmlNodes List of MathML nodes. 301 * @private 302 */ 303cvox.SemanticTree.Node.prototype.removeMathmlNodes_ = function(mmlNodes) { 304 var mmlList = this.mathml; 305 for (var i = 0, mml; mml = mmlNodes[i]; i++) { 306 var index = mmlList.indexOf(mml); 307 if (index != -1) { 308 mmlList.splice(index, 1); 309 } 310 } 311 this.mathml = mmlList; 312}; 313 314 315/** 316 * Appends a child to the node. 317 * @param {cvox.SemanticTree.Node} child The new child. 318 * @private 319 */ 320cvox.SemanticTree.Node.prototype.appendChild_ = function(child) { 321 this.childNodes.push(child); 322 this.addMathmlNodes_(child.mathml); 323 child.parent = this; 324}; 325 326 327/** 328 * Replaces a child node of the node. 329 * @param {!cvox.SemanticTree.Node} oldNode The node to be replaced. 330 * @param {!cvox.SemanticTree.Node} newNode The new node. 331 * @private 332 */ 333cvox.SemanticTree.Node.prototype.replaceChild_ = function(oldNode, newNode) { 334 var index = this.childNodes.indexOf(oldNode); 335 if (index == -1) { 336 return; 337 } 338 newNode.parent = this; 339 oldNode.parent = null; 340 this.childNodes[index] = newNode; 341 // To not mess up the order of MathML elements more than necessary, we only 342 // remove and add difference lists. The hope is that we might end up with 343 // little change. 344 var removeMathml = oldNode.mathml.filter( 345 function(x) {return newNode.mathml.indexOf(x) == -1;}); 346 var addMathml = newNode.mathml.filter( 347 function(x) {return oldNode.mathml.indexOf(x) == -1;}); 348 this.removeMathmlNodes_(removeMathml); 349 this.addMathmlNodes_(addMathml); 350}; 351 352 353/** 354 * Appends a content node to the node. 355 * @param {cvox.SemanticTree.Node} node The new content node. 356 * @private 357 */ 358cvox.SemanticTree.Node.prototype.appendContentNode_ = function(node) { 359 if (node) { 360 this.contentNodes.push(node); 361 this.addMathmlNodes_(node.mathml); 362 node.parent = this; 363 } 364}; 365 366 367/** 368 * Removes a content node from the node. 369 * @param {cvox.SemanticTree.Node} node The content node to be removed. 370 * @private 371 */ 372cvox.SemanticTree.Node.prototype.removeContentNode_ = function(node) { 373 if (node) { 374 var index = this.contentNodes.indexOf(node); 375 if (index != -1) { 376 this.contentNodes.splice(index, 1); 377 } 378 } 379}; 380 381 382/** 383 * This is the main function that creates the semantic tree by recursively 384 * parsing the initial MathML tree and bottom up assembling the tree. 385 * @param {!Element} mml The MathML tree. 386 * @return {!cvox.SemanticTree.Node} The root of the new tree. 387 * @private 388 */ 389cvox.SemanticTree.prototype.parseMathml_ = function(mml) { 390 var children = cvox.DomUtil.toArray(mml.children); 391 switch (cvox.SemanticUtil.tagName(mml)) { 392 case 'MATH': 393 case 'MROW': 394 case 'MPADDED': 395 case 'MSTYLE': 396 children = cvox.SemanticUtil.purgeNodes(children); 397 // Single child node, i.e. the row is meaningless. 398 if (children.length == 1) { 399 return this.parseMathml_(/** @type {!Element} */(children[0])); 400 } 401 // Case of a 'meaningful' row, even if they are empty. 402 return this.processRow_(this.parseMathmlChildren_(children)); 403 break; 404 case 'MFRAC': 405 var newNode = this.makeBranchNode_( 406 cvox.SemanticAttr.Type.FRACTION, 407 [this.parseMathml_(children[0]), this.parseMathml_(children[1])], 408 []); 409 newNode.role = cvox.SemanticAttr.Role.DIVISION; 410 return newNode; 411 break; 412 case 'MSUB': 413 case 'MSUP': 414 case 'MSUBSUP': 415 case 'MOVER': 416 case 'MUNDER': 417 case 'MUNDEROVER': 418 return this.makeLimitNode_(cvox.SemanticUtil.tagName(mml), 419 this.parseMathmlChildren_(children)); 420 break; 421 case 'MROOT': 422 return this.makeBranchNode_( 423 cvox.SemanticAttr.Type.ROOT, 424 [this.parseMathml_(children[0]), this.parseMathml_(children[1])], 425 []); 426 break; 427 case 'MSQRT': 428 children = this.parseMathmlChildren_( 429 cvox.SemanticUtil.purgeNodes(children)); 430 return this.makeBranchNode_( 431 cvox.SemanticAttr.Type.SQRT, [this.processRow_(children)], []); 432 break; 433 case 'MTABLE': 434 newNode = this.makeBranchNode_( 435 cvox.SemanticAttr.Type.TABLE, 436 this.parseMathmlChildren_(children), []); 437 if (cvox.SemanticTree.tableIsMultiline_(newNode)) { 438 this.tableToMultiline_(newNode); 439 } 440 return newNode; 441 break; 442 case 'MTR': 443 newNode = this.makeBranchNode_( 444 cvox.SemanticAttr.Type.ROW, 445 this.parseMathmlChildren_(children), []); 446 newNode.role = cvox.SemanticAttr.Role.TABLE; 447 return newNode; 448 break; 449 case 'MTD': 450 children = this.parseMathmlChildren_( 451 cvox.SemanticUtil.purgeNodes(children)); 452 newNode = this.makeBranchNode_( 453 cvox.SemanticAttr.Type.CELL, [this.processRow_(children)], []); 454 newNode.role = cvox.SemanticAttr.Role.TABLE; 455 return newNode; 456 break; 457 case 'MTEXT': 458 var leaf = this.makeLeafNode_(mml); 459 leaf.type = cvox.SemanticAttr.Type.TEXT; 460 return leaf; 461 break; 462 // TODO (sorge) Role and font of multi-character and digits unicode strings. 463 // TODO (sorge) Reclassify wrongly tagged numbers or identifiers. 464 // TODO (sorge) Put this all in a single clean reclassification method. 465 case 'MI': 466 leaf = this.makeLeafNode_(mml); 467 if (leaf.type == cvox.SemanticAttr.Type.UNKNOWN) { 468 leaf.type = cvox.SemanticAttr.Type.IDENTIFIER; 469 } 470 return leaf; 471 break; 472 case 'MN': 473 leaf = this.makeLeafNode_(mml); 474 if (leaf.type == cvox.SemanticAttr.Type.UNKNOWN) { 475 leaf.type = cvox.SemanticAttr.Type.NUMBER; 476 } 477 return leaf; 478 break; 479 case 'MO': 480 leaf = this.makeLeafNode_(mml); 481 if (leaf.type == cvox.SemanticAttr.Type.UNKNOWN) { 482 leaf.type = cvox.SemanticAttr.Type.OPERATOR; 483 } 484 return leaf; 485 break; 486 // TODO (sorge) Do something useful with error and phantom symbols. 487 default: 488 // Ordinarilly at this point we should not get any other tag. 489 return this.makeUnprocessed_(mml); 490 } 491}; 492 493 494/** 495 * Parse a list of MathML nodes into the semantic tree. 496 * @param {Array.<Element>} mmls A list of MathML nodes. 497 * @return {!Array.<cvox.SemanticTree.Node>} The list of resulting semantic 498 * node. 499 * @private 500 */ 501cvox.SemanticTree.prototype.parseMathmlChildren_ = function(mmls) { 502 var result = []; 503 for (var i = 0, mml; mml = mmls[i]; i++) { 504 result.push(this.parseMathml_(mml)); 505 } 506 return result; 507}; 508 509/** 510 * Create a node that is to be processed at a later point in time. 511 * @param {Node} mml The MathML tree. 512 * @return {!cvox.SemanticTree.Node} The new node. 513 * @private 514 */ 515cvox.SemanticTree.prototype.makeUnprocessed_ = function(mml) { 516 var node = this.createNode_(); 517 node.mathml = [mml]; 518 return node; 519}; 520 521 522/** 523 * Create an empty leaf node. 524 * @return {!cvox.SemanticTree.Node} The new node. 525 * @private 526 */ 527cvox.SemanticTree.prototype.makeEmptyNode_ = function() { 528 var node = this.createNode_(); 529 node.type = cvox.SemanticAttr.Type.EMPTY; 530 return node; 531}; 532 533 534/** 535 * Create a leaf node. 536 * @param {Node} mml The MathML tree. 537 * @return {!cvox.SemanticTree.Node} The new node. 538 * @private 539 */ 540cvox.SemanticTree.prototype.makeLeafNode_ = function(mml) { 541 var node = this.createNode_(); 542 node.mathml = [mml]; 543 node.updateContent_(mml.textContent); 544 node.font = mml.getAttribute('mathvariant') || node.font; 545 return node; 546}; 547 548 549/** 550 * Create a branching node. 551 * @param {!cvox.SemanticAttr.Type} type The type of the node. 552 * @param {!Array.<cvox.SemanticTree.Node>} children The child nodes. 553 * @param {!Array.<cvox.SemanticTree.Node>} contentNodes The content Nodes. 554 * @param {string=} content Content string if there is any. 555 * @return {!cvox.SemanticTree.Node} The new node. 556 * @private 557 */ 558cvox.SemanticTree.prototype.makeBranchNode_ = function( 559 type, children, contentNodes, content) { 560 var node = this.createNode_(); 561 if (content) { 562 node.updateContent_(content); 563 } 564 node.type = type; 565 node.childNodes = children; 566 node.contentNodes = contentNodes; 567 children.concat(contentNodes) 568 .forEach( 569 function(x) { 570 x.parent = node; 571 node.addMathmlNodes_(x.mathml); 572 }); 573 return node; 574}; 575 576 577/** 578 * Create a branching node for an implicit operation, currently assumed to 579 * be of multiplicative type. 580 * @param {!Array.<!cvox.SemanticTree.Node>} nodes The operands. 581 * @return {!cvox.SemanticTree.Node} The new branch node. 582 * @private 583 */ 584cvox.SemanticTree.prototype.makeImplicitNode_ = function(nodes) { 585 if (nodes.length == 1) { 586 return nodes[0]; 587 } 588 var operator = this.createNode_(); 589 // For now we assume this is a multiplication using invisible times. 590 operator.updateContent_(cvox.SemanticAttr.invisibleTimes()); 591 var newNode = this.makeInfixNode_(nodes, operator); 592 newNode.role = cvox.SemanticAttr.Role.IMPLICIT; 593 return newNode; 594}; 595 596 597/** 598 * Create a branching node for an infix operation. 599 * @param {!Array.<cvox.SemanticTree.Node>} children The operands. 600 * @param {!cvox.SemanticTree.Node} opNode The operator. 601 * @return {!cvox.SemanticTree.Node} The new branch node. 602 * @private 603 */ 604cvox.SemanticTree.prototype.makeInfixNode_ = function(children, opNode) { 605 return this.makeBranchNode_( 606 cvox.SemanticAttr.Type.INFIXOP, children, [opNode], opNode.textContent); 607}; 608 609 610/** 611 * Creates a node of the specified type by collapsing the given node list into 612 * one content (thereby concatenating the content of each node into a single 613 * content string) with the inner node as a child. 614 * @param {!cvox.SemanticTree.Node} inner The inner node. 615 * @param {!Array.<cvox.SemanticTree.Node>} nodeList List of nodes. 616 * @param {!cvox.SemanticAttr.Type} type The new type of the node. 617 * @return {!cvox.SemanticTree.Node} The new branch node. 618 * @private 619 */ 620cvox.SemanticTree.prototype.makeConcatNode_ = function(inner, nodeList, type) { 621 if (nodeList.length == 0) { 622 return inner; 623 } 624 var content = nodeList.map(function(x) {return x.textContent;}).join(' '); 625 var newNode = this.makeBranchNode_(type, [inner], nodeList, content); 626 if (nodeList.length > 0) { 627 newNode.role = cvox.SemanticAttr.Role.MULTIOP; 628 } 629 return newNode; 630}; 631 632 633/** 634 * Wraps a node into prefix operators. 635 * Example: + - a becomes (+ (- (a))) 636 * Input: a [+, -] -> Output: content: '+ -', child: a 637 * @param {!cvox.SemanticTree.Node} node The inner node. 638 * @param {!Array.<cvox.SemanticTree.Node>} prefixes Prefix operators 639 * from the outermost to the innermost. 640 * @return {!cvox.SemanticTree.Node} The new branch node. 641 * @private 642 */ 643cvox.SemanticTree.prototype.makePrefixNode_ = function(node, prefixes) { 644 var negatives = cvox.SemanticTree.partitionNodes_( 645 prefixes, cvox.SemanticTree.attrPred_('role', 'SUBTRACTION')); 646 var newNode = this.makeConcatNode_( 647 node, negatives.comp.pop(), cvox.SemanticAttr.Type.PREFIXOP); 648 649 while (negatives.rel.length > 0) { 650 newNode = this.makeConcatNode_( 651 newNode, [negatives.rel.pop()], cvox.SemanticAttr.Type.PREFIXOP); 652 newNode.role = cvox.SemanticAttr.Role.NEGATIVE; 653 newNode = this.makeConcatNode_( 654 newNode, negatives.comp.pop(), cvox.SemanticAttr.Type.PREFIXOP); 655 } 656 return newNode; 657}; 658 659 660/** 661 * Wraps a node into postfix operators. 662 * Example: a - + becomes (((a) -) +) 663 * Input: a [-, +] -> Output: content: '- +', child: a 664 * @param {!cvox.SemanticTree.Node} node The inner node. 665 * @param {!Array.<cvox.SemanticTree.Node>} postfixes Postfix operators from 666 * innermost to outermost. 667 * @return {!cvox.SemanticTree.Node} The new branch node. 668 * @private 669 */ 670cvox.SemanticTree.prototype.makePostfixNode_ = function(node, postfixes) { 671 return this.makeConcatNode_( 672 node, postfixes, cvox.SemanticAttr.Type.POSTFIXOP); 673}; 674 675 676// TODO (sorge) Separate out interspersed text before the relations in row 677// heuristic otherwise we get them as implicit operations! 678// Currently we handle that later in the rules, which is rather messy. 679/** 680 * Processes a list of nodes, combining expressions by delimiters, tables, 681 * punctuation sequences, function/big operator/integral applications to 682 * generate a syntax tree with relation and operator precedence. 683 * 684 * This is the main heuristic to rewrite a flat row of terms into a meaningful 685 * term tree. 686 * @param {!Array.<cvox.SemanticTree.Node>} nodes The list of nodes. 687 * @return {!cvox.SemanticTree.Node} The root node of the syntax tree. 688 * @private 689 */ 690cvox.SemanticTree.prototype.processRow_ = function(nodes) { 691 if (nodes.length == 0) { 692 return this.makeEmptyNode_(); 693 } 694 nodes = this.getFencesInRow_(nodes); 695 nodes = this.processTablesInRow_(nodes); 696 nodes = this.getPunctuationInRow_(nodes); 697 nodes = this.getFunctionsInRow_(nodes); 698 return this.processRelationsInRow_(nodes); 699}; 700 701 702/** 703 * Constructs a syntax tree with relation and operator precedence from a list 704 * of nodes. 705 * @param {!Array.<!cvox.SemanticTree.Node>} nodes The list of nodes. 706 * @return {!cvox.SemanticTree.Node} The root node of the syntax tree. 707 * @private 708 */ 709cvox.SemanticTree.prototype.processRelationsInRow_ = function(nodes) { 710 var partition = cvox.SemanticTree.partitionNodes_( 711 nodes, cvox.SemanticTree.attrPred_('type', 'RELATION')); 712 var firstRel = partition.rel[0]; 713 714 if (!firstRel) { 715 return this.processOperationsInRow_(nodes); 716 } 717 if (nodes.length == 1) { 718 return nodes[0]; 719 } 720 var children = partition.comp.map( 721 goog.bind(this.processOperationsInRow_, this)); 722 if (partition.rel.every( 723 function(x) {return x.textContent == firstRel.textContent;})) { 724 return this.makeBranchNode_( 725 cvox.SemanticAttr.Type.RELSEQ, children, partition.rel, 726 firstRel.textContent); 727 } 728 return this.makeBranchNode_( 729 cvox.SemanticAttr.Type.MULTIREL, children, partition.rel); 730}; 731 732 733/** 734 * Constructs a syntax tree with operator precedence from a list nodes. 735 * @param {!Array.<!cvox.SemanticTree.Node>} nodes The list of nodes. 736 * @return {!cvox.SemanticTree.Node} The root node of the syntax tree. 737 * @private 738 */ 739cvox.SemanticTree.prototype.processOperationsInRow_ = function(nodes) { 740 if (nodes.length == 0) { 741 return this.makeEmptyNode_(); 742 } 743 if (nodes.length == 1) { 744 return nodes[0]; 745 } 746 747 var prefix = []; 748 while (nodes.length > 0 && 749 nodes[0].type == cvox.SemanticAttr.Type.OPERATOR) { 750 prefix.push(nodes.shift()); 751 } 752 // Pathological case: only operators in row. 753 if (nodes.length == 0) { 754 return this.makePrefixNode_(prefix.pop(), prefix); 755 } 756 if (nodes.length == 1) { 757 return this.makePrefixNode_(nodes[0], prefix); 758 } 759 760 var split = cvox.SemanticTree.sliceNodes_( 761 nodes, cvox.SemanticTree.attrPred_('type', 'OPERATOR')); 762 // At this point, we know that split.head is not empty! 763 var node = this.makePrefixNode_( 764 this.makeImplicitNode_( 765 /** @type {!Array.<!cvox.SemanticTree.Node>} */ (split.head)), 766 prefix); 767 if (!split.div) { 768 return node; 769 } 770 return this.makeOperationsTree_(split.tail, node, split.div); 771}; 772 773 774/** 775 * Recursively constructs syntax tree with operator precedence from a list nodes 776 * given a initial root node. 777 * @param {!Array.<cvox.SemanticTree.Node>} nodes The list of nodes. 778 * @param {!cvox.SemanticTree.Node} root Initial tree. 779 * @param {!cvox.SemanticTree.Node} lastop Last operator that has not been 780 * processed yet. 781 * @param {Array.<cvox.SemanticTree.Node>=} prefixes Operator nodes that will 782 * become prefix operation (or postfix in case they come after last operand). 783 * @return {!cvox.SemanticTree.Node} The root node of the syntax tree. 784 * @private 785 */ 786cvox.SemanticTree.prototype.makeOperationsTree_ = function( 787 nodes, root, lastop, prefixes) { 788 prefixes = prefixes || []; 789 790 if (nodes.length == 0) { 791 // Left over prefixes become postfixes. 792 prefixes.unshift(lastop); 793 if (root.type == cvox.SemanticAttr.Type.INFIXOP) { 794 // We assume prefixes bind stronger than postfixes. 795 var node = this.makePostfixNode_( 796 // Here we know that the childNodes are not empty! 797 /** @type {!cvox.SemanticTree.Node} */ (root.childNodes.pop()), 798 prefixes); 799 root.appendChild_(node); 800 return root; 801 } 802 return this.makePostfixNode_(root, prefixes); 803 } 804 805 var split = cvox.SemanticTree.sliceNodes_( 806 nodes, cvox.SemanticTree.attrPred_('type', 'OPERATOR')); 807 808 if (split.head.length == 0) { 809 prefixes.push(split.div); 810 return this.makeOperationsTree_(split.tail, root, lastop, prefixes); 811 } 812 813 var node = this.makePrefixNode_( 814 this.makeImplicitNode_(split.head), prefixes); 815 var newNode = this.appendOperand_(root, lastop, node); 816 if (!split.div) { 817 return newNode; 818 } 819 820 return this.makeOperationsTree_(split.tail, newNode, split.div, []); 821}; 822 823// TODO (sorge) The following four functions could be combined into 824// a single one. Currently it is clearer the way it is, though. 825/** 826 * Appends an operand at the right place in an operator tree. 827 * @param {!cvox.SemanticTree.Node} root The operator tree. 828 * @param {!cvox.SemanticTree.Node} op The operator node. 829 * @param {!cvox.SemanticTree.Node} node The node to be added. 830 * @return {!cvox.SemanticTree.Node} The modified root node. 831 * @private 832 */ 833cvox.SemanticTree.prototype.appendOperand_ = function(root, op, node) { 834 // In general our operator tree will have the form that additions and 835 // subtractions are stacked, while multiplications are subordinate. 836 if (root.type != cvox.SemanticAttr.Type.INFIXOP) { 837 return this.makeInfixNode_([root, node], op); 838 } 839 if (this.appendExistingOperator_(root, op, node)) { 840 return root; 841 } 842 return op.role == cvox.SemanticAttr.Role.MULTIPLICATION ? 843 this.appendMultiplicativeOp_(root, op, node) : 844 this.appendAdditiveOp_(root, op, node); 845}; 846 847 848/** 849 * Appends a multiplicative operator and operand. 850 * @param {!cvox.SemanticTree.Node} root The root node. 851 * @param {!cvox.SemanticTree.Node} op The operator node. 852 * @param {!cvox.SemanticTree.Node} node The operand node to be added. 853 * @return {!cvox.SemanticTree.Node} The modified root node. 854 * @private 855 */ 856cvox.SemanticTree.prototype.appendMultiplicativeOp_ = function(root, op, node) { 857 var lastRoot = root; 858 var lastChild = root.childNodes[root.childNodes.length - 1]; 859 while (lastChild && lastChild.type == cvox.SemanticAttr.Type.INFIXOP) { 860 lastRoot = lastChild; 861 lastChild = lastRoot.childNodes[root.childNodes.length - 1]; 862 } 863 var newNode = this.makeInfixNode_([lastRoot.childNodes.pop(), node], op); 864 lastRoot.appendChild_(newNode); 865 return root; 866}; 867 868 869/** 870 * Appends an additive/substractive operator and operand. 871 * @param {!cvox.SemanticTree.Node} root The old root node. 872 * @param {!cvox.SemanticTree.Node} op The operator node. 873 * @param {!cvox.SemanticTree.Node} node The operand node to be added. 874 * @return {!cvox.SemanticTree.Node} The new root node. 875 * @private 876 */ 877cvox.SemanticTree.prototype.appendAdditiveOp_ = function(root, op, node) { 878 return this.makeInfixNode_([root, node], op); 879}; 880 881 882/** 883 * Adds an operand to an operator node if it is the continuation of an existing 884 * operation. 885 * @param {!cvox.SemanticTree.Node} root The root node. 886 * @param {!cvox.SemanticTree.Node} op The operator node. 887 * @param {!cvox.SemanticTree.Node} node The operand node to be added. 888 * @return {boolean} True if operator was successfully appended. 889 * @private 890 */ 891cvox.SemanticTree.prototype.appendExistingOperator_ = function(root, op, node) { 892 if (!root || root.type != cvox.SemanticAttr.Type.INFIXOP) { 893 return false; 894 } 895 if (root.textContent == op.textContent) { 896 root.appendContentNode_(op); 897 root.appendChild_(node); 898 return true; 899 } 900 this.appendExistingOperator_( 901 // Again, if this is an INFIXOP node, we know it has a child! 902 /** @type {!cvox.SemanticTree.Node} */ 903 (root.childNodes[root.childNodes.length - 1]), 904 op, node); 905}; 906 907 908// TODO (sorge) The following procedure needs a rational reconstruction. It 909// contains a number of similar cases which should be combined. 910/** 911 * Combines delimited expressions in a list of nodes. 912 * 913 * The basic idea of the heuristic is as follows: 914 * 1. Opening and closing delimiters are matched regardless of the actual shape 915 * of the fence. These are turned into fenced nodes. 916 * 2. Neutral fences are matched only with neutral fences of the same shape. 917 * 3. For a collection of unmatched neutral fences we try to get a maximum 918 * number of matching fences. E.g. || a|b || would be turned into a fenced 919 * node with fences || and content a|b. 920 * 4. Any remaining unmatched delimiters are turned into punctuation nodes. 921 * @param {!Array.<!cvox.SemanticTree.Node>} nodes The list of nodes. 922 * @return {!Array.<!cvox.SemanticTree.Node>} The new list of nodes. 923 * @private 924 */ 925cvox.SemanticTree.prototype.getFencesInRow_ = function(nodes) { 926 var partition = cvox.SemanticTree.partitionNodes_( 927 nodes, cvox.SemanticTree.attrPred_('type', 'FENCE')); 928 var felem = partition.comp.shift(); 929 return this.processFences_(partition.rel, partition.comp, [], [felem]); 930}; 931 932 933/** 934 * Recursively processes a list of nodes and combines all the fenced expressions 935 * into single nodes. It also processes singular fences, building expressions 936 * that are only fenced left or right. 937 * @param {!Array.<cvox.SemanticTree.Node>} fences FIFO queue of fence nodes. 938 * @param {!Array.<Array.<cvox.SemanticTree.Node>>} content FIFO queue content 939 * between fences. 940 * @param {!Array.<cvox.SemanticTree.Node>} openStack LIFO stack of open fences. 941 * @param {!Array.<!Array.<cvox.SemanticTree.Node>>} contentStack LIFO stack of 942 * content between fences yet to be processed. 943 * @return {!Array.<cvox.SemanticTree.Node>} A list of nodes with all fenced 944 * expressions processed. 945 * @private 946 */ 947cvox.SemanticTree.prototype.processFences_ = function( 948 fences, content, openStack, contentStack) { 949 // Base case 1: Everything is used up. 950 if (fences.length == 0 && openStack.length == 0) { 951 return contentStack[0]; 952 } 953 var openPred = cvox.SemanticTree.attrPred_('role', 'OPEN'); 954 // Base case 2: Only open and neutral fences are left on the stack. 955 if (fences.length == 0) { 956 // Basic idea: 957 // - make punctuation nodes from open fences 958 // - combine as many neutral fences as possible, if the are not separated by 959 // open fences. 960 // The idea is to allow for things like case statements etc. and not bury 961 // them inside a neutral fenced expression. 962 // 963 // 0. We process the list from left to right. Hence the first element on the 964 // content stack are actually left most elements in the expression. 965 // 1. Slice at open fence. 966 // 2. On tail optimize for neutral fences. 967 // 3. Repeat until fence stack is exhausted. 968 // Push rightmost elements onto the result. 969 var result = contentStack.shift(); 970 while (openStack.length > 0) { 971 if (openPred(openStack[0])) { 972 var firstOpen = openStack.shift(); 973 cvox.SemanticTree.fenceToPunct_(firstOpen); 974 result.push(firstOpen); 975 } else { 976 var split = cvox.SemanticTree.sliceNodes_(openStack, openPred); 977 var cutLength = split.head.length - 1; 978 var innerNodes = this.processNeutralFences_( 979 split.head, contentStack.slice(0, cutLength)); 980 contentStack = contentStack.slice(cutLength); 981 //var rightContent = contentStack.shift(); 982 result.push.apply(result, innerNodes); 983 //result.push.apply(result, rightContent); 984 if (split.div) { 985 split.tail.unshift(split.div); 986 } 987 openStack = split.tail; 988 } 989 result.push.apply(result, contentStack.shift()); 990 } 991 return result; 992 } 993 var lastOpen = openStack[openStack.length - 1]; 994 var firstRole = fences[0].role; 995 // General opening case. 996 // Either we have an open fence. 997 if (firstRole == cvox.SemanticAttr.Role.OPEN || 998 // Or we have a neutral fence that does not have a counter part. 999 (firstRole == cvox.SemanticAttr.Role.NEUTRAL && 1000 (!lastOpen || 1001 fences[0].textContent != lastOpen.textContent))) { 1002 openStack.push(fences.shift()); 1003 contentStack.push(content.shift()); 1004 return this.processFences_(fences, content, openStack, contentStack); 1005 } 1006 // General closing case. 1007 if (lastOpen && ( 1008 // Closing fence for some opening fence. 1009 (firstRole == cvox.SemanticAttr.Role.CLOSE && 1010 lastOpen.role == cvox.SemanticAttr.Role.OPEN) || 1011 // Netural fence with exact counter part. 1012 (firstRole == cvox.SemanticAttr.Role.NEUTRAL && 1013 fences[0].textContent == lastOpen.textContent))) { 1014 var fenced = this.makeHorizontalFencedNode_( 1015 openStack.pop(), fences.shift(), contentStack.pop()); 1016 contentStack.push(contentStack.pop().concat([fenced], content.shift())); 1017 return this.processFences_(fences, content, openStack, contentStack); 1018 } 1019 // Closing with a neutral fence on the stack. 1020 if (lastOpen && firstRole == cvox.SemanticAttr.Role.CLOSE && 1021 lastOpen.role == cvox.SemanticAttr.Role.NEUTRAL && 1022 openStack.some(openPred)) { 1023 // Steps of the algorithm: 1024 // 1. Split list at right most opening bracket. 1025 // 2. Cut content list at corresponding length. 1026 // 3. Optimise the neutral fences. 1027 // 4. Make fenced node. 1028 // 1029 // Careful, this reverses openStack! 1030 var split = cvox.SemanticTree.sliceNodes_(openStack, openPred, true); 1031 // We know that 1032 // (a) div & tail exist, 1033 // (b) all are combined in this step into a single fenced node, 1034 // (c) head is the new openStack, 1035 // (d) the new contentStack is remainder of contentStack + new fenced node + 1036 // shift of content. 1037 var rightContent = contentStack.pop(); 1038 var cutLength = contentStack.length - split.tail.length + 1; 1039 var innerNodes = this.processNeutralFences_( 1040 split.tail, contentStack.slice(cutLength)); 1041 contentStack = contentStack.slice(0, cutLength); 1042 var fenced = this.makeHorizontalFencedNode_( 1043 split.div, fences.shift(), 1044 contentStack.pop().concat(innerNodes, rightContent)); 1045 contentStack.push(contentStack.pop().concat([fenced], content.shift())); 1046 return this.processFences_(fences, content, split.head, contentStack); 1047 } 1048 // Final Case: A singular closing fence. 1049 // We turn the fence into a punctuation. 1050 var fenced = fences.shift(); 1051 cvox.SemanticTree.fenceToPunct_(fenced); 1052 contentStack.push(contentStack.pop().concat([fenced], content.shift())); 1053 return this.processFences_(fences, content, openStack, contentStack); 1054}; 1055 1056 1057// TODO (sorge) The following could be done with linear programming. 1058/** 1059 * Trys to combine neutral fences as much as possible. 1060 * @param {!Array.<!cvox.SemanticTree.Node>} fences A list of neutral fences. 1061 * @param {!Array.<!Array.<cvox.SemanticTree.Node>>} content Intermediate 1062 * content. Observe that |content| = |fences| - 1 1063 * @return {!Array.<cvox.SemanticTree.Node>} List of node with fully fenced 1064 * nodes. 1065 * @private 1066 */ 1067cvox.SemanticTree.prototype.processNeutralFences_ = function(fences, content) { 1068 if (fences.length == 0) { 1069 return fences; 1070 } 1071 if (fences.length == 1) { 1072 cvox.SemanticTree.fenceToPunct_(fences[0]); 1073 return fences; 1074 } 1075 var firstFence = fences.shift(); 1076 var split = cvox.SemanticTree.sliceNodes_( 1077 fences, function(x) {return x.textContent == firstFence.textContent;}); 1078 if (!split.div) { 1079 cvox.SemanticTree.fenceToPunct_(firstFence); 1080 var restContent = content.shift(); 1081 restContent.unshift(firstFence); 1082 return restContent.concat(this.processNeutralFences_(fences, content)); 1083 } 1084 var newContent = this.combineFencedContent_( 1085 firstFence, split.div, split.head, content); 1086 if (split.tail.length > 0) { 1087 var leftContent = newContent.shift(); 1088 var result = this.processNeutralFences_(split.tail, newContent); 1089 return leftContent.concat(result); 1090 } 1091 return newContent[0]; 1092}; 1093 1094 1095/** 1096 * Combines nodes framed by two matching fences using the given content. 1097 * Example: leftFence: [, rightFence: ], midFences: |, | 1098 * content: c1, c2, c3, c4, ... cn 1099 * return: [c1 | c2 | c3 ], c4, ... cn 1100 * @param {!cvox.SemanticTree.Node} leftFence The left fence. 1101 * @param {!cvox.SemanticTree.Node} rightFence The right fence. 1102 * @param {!Array.<cvox.SemanticTree.Node>} midFences A list of intermediate 1103 * fences. 1104 * @param {!Array.<!Array.<cvox.SemanticTree.Node>>} content Intermediate 1105 * content. Observe that |content| = |fences| - 1 + k where k >= 0 is the 1106 * remainder. 1107 * @return {!Array.<!Array.<cvox.SemanticTree.Node>>} List of content nodes 1108 * where the first is the fully fenced node wrt. the given left and right 1109 * fence. 1110 * @private 1111 */ 1112cvox.SemanticTree.prototype.combineFencedContent_ = function( 1113 leftFence, rightFence, midFences, content) { 1114 1115 if (midFences.length == 0) { 1116 var fenced = this.makeHorizontalFencedNode_( 1117 leftFence, rightFence, content.shift()); 1118 content.unshift(fenced); 1119 return content; 1120 } 1121 1122 var leftContent = content.shift(); 1123 var cutLength = midFences.length - 1; 1124 var midContent = content.slice(0, cutLength); 1125 content = content.slice(cutLength); 1126 var rightContent = content.shift(); 1127 var innerNodes = this.processNeutralFences_(midFences, midContent); 1128 leftContent.push.apply(leftContent, innerNodes); 1129 leftContent.push.apply(leftContent, rightContent); 1130 var fenced = this.makeHorizontalFencedNode_( 1131 leftFence, rightFence, leftContent); 1132 if (content.length > 0) { 1133 content[0].unshift(fenced); 1134 } else { 1135 content = [[fenced]]; 1136 } 1137 return content; 1138 }; 1139 1140 1141/** 1142 * Rewrite fences into punctuation. This is done with any "leftover" fence. 1143 * @param {cvox.SemanticTree.Node} fence Fence. 1144 * @private 1145 */ 1146cvox.SemanticTree.fenceToPunct_ = function(fence) { 1147 fence.type = cvox.SemanticAttr.Type.PUNCTUATION; 1148 switch (fence.role) { 1149 case cvox.SemanticAttr.Role.NEUTRAL: 1150 fence.role = cvox.SemanticAttr.Role.VBAR; 1151 break; 1152 case cvox.SemanticAttr.Role.OPEN: 1153 fence.role = cvox.SemanticAttr.Role.OPENFENCE; 1154 break; 1155 case cvox.SemanticAttr.Role.CLOSE: 1156 fence.role = cvox.SemanticAttr.Role.CLOSEFENCE; 1157 break; 1158 } 1159}; 1160 1161 1162/** 1163 * Create a fenced node. 1164 * @param {cvox.SemanticTree.Node} ofence Opening fence. 1165 * @param {cvox.SemanticTree.Node} cfence Closing fence. 1166 * @param {!Array.<cvox.SemanticTree.Node>} content The content 1167 * between the fences. 1168 * @return {!cvox.SemanticTree.Node} The new node. 1169 * @private 1170 */ 1171cvox.SemanticTree.prototype.makeHorizontalFencedNode_ = function( 1172 ofence, cfence, content) { 1173 var childNode = this.processRow_(content); 1174 var newNode = this.makeBranchNode_( 1175 cvox.SemanticAttr.Type.FENCED, [childNode], [ofence, cfence]); 1176 if (ofence.role == cvox.SemanticAttr.Role.OPEN) { 1177 newNode.role = cvox.SemanticAttr.Role.LEFTRIGHT; 1178 } else { 1179 newNode.role = ofence.role; 1180 } 1181 return newNode; 1182}; 1183 1184 1185/** 1186 * Combines sequences of punctuated expressions in a list of nodes. 1187 * @param {!Array.<cvox.SemanticTree.Node>} nodes The list of nodes. 1188 * @return {!Array.<cvox.SemanticTree.Node>} The new list of nodes. 1189 * @private 1190 */ 1191cvox.SemanticTree.prototype.getPunctuationInRow_ = function(nodes) { 1192 // For now we just make a punctuation node with a particular role. This is 1193 // similar to an mrow. The only exception are ellipses, which we assume to be 1194 // in lieu of identifiers. 1195 // In addition we keep the single punctuation nodes as content. 1196 var partition = cvox.SemanticTree.partitionNodes_( 1197 nodes, function(x) { 1198 return cvox.SemanticTree.attrPred_('type', 'PUNCTUATION')(x) && 1199 !cvox.SemanticTree.attrPred_('role', 'ELLIPSIS')(x);}); 1200 if (partition.rel.length == 0) { 1201 return nodes; 1202 } 1203 var newNodes = []; 1204 var firstComp = partition.comp.shift(); 1205 if (firstComp.length > 0) { 1206 newNodes.push(this.processRow_(firstComp)); 1207 } 1208 var relCounter = 0; 1209 while (partition.comp.length > 0) { 1210 newNodes.push(partition.rel[relCounter++]); 1211 firstComp = partition.comp.shift(); 1212 if (firstComp.length > 0) { 1213 newNodes.push(this.processRow_(firstComp)); 1214 } 1215 } 1216 return [this.makePunctuatedNode_(newNodes, partition.rel)]; 1217}; 1218 1219 1220/** 1221 * Create a punctuated node. 1222 * @param {!Array.<!cvox.SemanticTree.Node>} nodes List of all nodes separated 1223 * by punctuations. 1224 * @param {!Array.<!cvox.SemanticTree.Node>} punctuations List of all separating 1225 * punctations. Observe that punctations is a subset of nodes. 1226 * @return {!cvox.SemanticTree.Node} 1227 * @private 1228 */ 1229cvox.SemanticTree.prototype.makePunctuatedNode_ = function( 1230 nodes, punctuations) { 1231 var newNode = this.makeBranchNode_( 1232 cvox.SemanticAttr.Type.PUNCTUATED, nodes, punctuations); 1233 1234 if (punctuations.length == 1 && 1235 nodes[0].type == cvox.SemanticAttr.Type.PUNCTUATION) { 1236 newNode.role = cvox.SemanticAttr.Role.STARTPUNCT; 1237 } else if (punctuations.length == 1 && 1238 nodes[nodes.length - 1].type == cvox.SemanticAttr.Type.PUNCTUATION) { 1239 newNode.role = cvox.SemanticAttr.Role.ENDPUNCT; 1240 } else { 1241 newNode.role = cvox.SemanticAttr.Role.SEQUENCE; 1242 } 1243 return newNode; 1244}; 1245 1246 1247/** 1248 * Creates a limit node from a sub/superscript or over/under node if the central 1249 * element is a big operator. Otherwise it creates the standard elements. 1250 * @param {string} mmlTag The tag name of the original node. 1251 * @param {!Array.<!cvox.SemanticTree.Node>} children The children of the 1252 * original node. 1253 * @return {!cvox.SemanticTree.Node} The newly created limit node. 1254 * @private 1255 */ 1256cvox.SemanticTree.prototype.makeLimitNode_ = function(mmlTag, children) { 1257 var center = children[0]; 1258 var isFunction = cvox.SemanticTree.attrPred_('type', 'FUNCTION')(center); 1259 // TODO (sorge) Put this into a single function. 1260 var isLimit = cvox.SemanticTree.attrPred_('type', 'LARGEOP')(center) || 1261 cvox.SemanticTree.attrPred_('type', 'LIMBOTH')(center) || 1262 cvox.SemanticTree.attrPred_('type', 'LIMLOWER')(center) || 1263 cvox.SemanticTree.attrPred_('type', 'LIMUPPER')(center) || 1264 (isFunction && cvox.SemanticTree.attrPred_('role', 'LIMFUNC')(center)); 1265 var type = cvox.SemanticAttr.Type.UNKNOWN; 1266 // TODO (sorge) Make use of the difference in information on sub vs under etc. 1267 if (isLimit) { 1268 switch (mmlTag) { 1269 case 'MSUB': 1270 case 'MUNDER': 1271 type = cvox.SemanticAttr.Type.LIMLOWER; 1272 break; 1273 case 'MSUP': 1274 case 'MOVER': 1275 type = cvox.SemanticAttr.Type.LIMUPPER; 1276 break; 1277 case 'MSUBSUP': 1278 case 'MUNDEROVER': 1279 type = cvox.SemanticAttr.Type.LIMBOTH; 1280 break; 1281 } 1282 } else { 1283 switch (mmlTag) { 1284 case 'MSUB': 1285 type = cvox.SemanticAttr.Type.SUBSCRIPT; 1286 break; 1287 case 'MSUP': 1288 type = cvox.SemanticAttr.Type.SUPERSCRIPT; 1289 break; 1290 case 'MSUBSUP': 1291 var innerNode = this.makeBranchNode_(cvox.SemanticAttr.Type.SUBSCRIPT, 1292 [center, children[1]], []); 1293 innerNode.role = center.role; 1294 children = [innerNode, children[2]]; 1295 type = cvox.SemanticAttr.Type.SUPERSCRIPT; 1296 break; 1297 case 'MOVER': 1298 type = cvox.SemanticAttr.Type.OVERSCORE; 1299 break; 1300 case 'MUNDER': 1301 type = cvox.SemanticAttr.Type.UNDERSCORE; 1302 break; 1303 case 'MUNDEROVER': 1304 default: 1305 var innerNode = this.makeBranchNode_(cvox.SemanticAttr.Type.UNDERSCORE, 1306 [center, children[1]], []); 1307 innerNode.role = center.role; 1308 children = [innerNode, children[2]]; 1309 type = cvox.SemanticAttr.Type.OVERSCORE; 1310 break; 1311 } 1312 } 1313 var newNode = this.makeBranchNode_(type, children, []); 1314 newNode.role = center.role; 1315 return newNode; 1316}; 1317 1318 1319/** 1320 * Recursive method to accumulate function expressions. 1321 * 1322 * The idea is to process functions in a row from left to right combining them 1323 * with there arguments. Thereby we take the notion of a function rather broadly 1324 * as a functional expressions that consists of a prefix and some arguments. 1325 * In particular we distinguish four types of functional expressions: 1326 * - integral: Integral expression. 1327 * - bigop: A big operator expression like a sum. 1328 * - prefix: A well defined prefix function such as sin, cos or a limit 1329 * functions like lim, max. 1330 * - simple: An expression consisting of letters that are potentially a function 1331 * symbol. If we have an explicit function application symbol 1332 * following the expression we turn into a prefix function. Otherwise 1333 * we decide heuristically if we could have a function application. 1334 * @param {!Array.<cvox.SemanticTree.Node>} restNodes The remainder list of 1335 * nodes. 1336 * @param {!Array.<cvox.SemanticTree.Node>=} result The result node list. 1337 * @return {!Array.<!cvox.SemanticTree.Node>} The fully processed list. 1338 * @private 1339 */ 1340cvox.SemanticTree.prototype.getFunctionsInRow_ = function(restNodes, result) { 1341 result = result || []; 1342 // Base case. 1343 if (restNodes.length == 0) { 1344 return result; 1345 } 1346 var firstNode = /** @type {!cvox.SemanticTree.Node} */ (restNodes.shift()); 1347 var heuristic = cvox.SemanticTree.classifyFunction_(firstNode, restNodes); 1348 // First node is not a function node. 1349 if (!heuristic) { 1350 result.push(firstNode); 1351 return this.getFunctionsInRow_(restNodes, result); 1352 } 1353 // Combine functions in the rest of the row. 1354 var processedRest = this.getFunctionsInRow_(restNodes, []); 1355 var newRest = this.getFunctionArgs_(firstNode, processedRest, heuristic); 1356 return result.concat(newRest); 1357}; 1358 1359 1360/** 1361 * Classifies a function wrt. the heuristic that should be applied. 1362 * @param {!cvox.SemanticTree.Node} funcNode The node to be classified. 1363 * @param {!Array.<cvox.SemanticTree.Node>} restNodes The remainder list of 1364 * nodes. They can useful to look ahead if there is an explicit function 1365 * application. If there is one, it will be destructively removed! 1366 * @return {!string} The string specifying the heuristic. 1367 * @private 1368 */ 1369cvox.SemanticTree.classifyFunction_ = function(funcNode, restNodes) { 1370 // We do not allow double function application. This is not lambda calculus! 1371 if (funcNode.type == cvox.SemanticAttr.Type.APPL || 1372 funcNode.type == cvox.SemanticAttr.Type.BIGOP || 1373 funcNode.type == cvox.SemanticAttr.Type.INTEGRAL) { 1374 return ''; 1375 } 1376 // Find and remove explicit function applications. 1377 // We now treat funcNode as a prefix function, regardless of what its actual 1378 // content is. 1379 if (restNodes[0] && 1380 restNodes[0].textContent == cvox.SemanticAttr.functionApplication()) { 1381 // Remove explicit function application. This is destructive on the 1382 // underlying list. 1383 restNodes.shift(); 1384 cvox.SemanticTree.propagatePrefixFunc_(funcNode); 1385 return 'prefix'; 1386 } 1387 switch (funcNode.role) { 1388 case cvox.SemanticAttr.Role.INTEGRAL: 1389 return 'integral'; 1390 break; 1391 case cvox.SemanticAttr.Role.SUM: 1392 return 'bigop'; 1393 break; 1394 case cvox.SemanticAttr.Role.PREFIXFUNC: 1395 case cvox.SemanticAttr.Role.LIMFUNC: 1396 return 'prefix'; 1397 break; 1398 default: 1399 if (funcNode.type == cvox.SemanticAttr.Type.IDENTIFIER) { 1400 return 'simple'; 1401 } 1402 } 1403 return ''; 1404}; 1405 1406 1407/** 1408 * Propagates a prefix function role in a node. 1409 * @param {cvox.SemanticTree.Node} funcNode The node whose role is to be 1410 * rewritten. 1411 * @private 1412 */ 1413cvox.SemanticTree.propagatePrefixFunc_ = function(funcNode) { 1414 if (funcNode) { 1415 funcNode.role = cvox.SemanticAttr.Role.PREFIXFUNC; 1416 cvox.SemanticTree.propagatePrefixFunc_(funcNode.childNodes[0]); 1417 } 1418}; 1419 1420 1421/** 1422 * Computes the arguments for a function from a list of nodes depending on the 1423 * given heuristic. 1424 * @param {!cvox.SemanticTree.Node} func A function node. 1425 * @param {!Array.<cvox.SemanticTree.Node>} rest List of nodes to choose 1426 * arguments from. 1427 * @param {string} heuristic The heuristic to follow. 1428 * @return {!Array.<!cvox.SemanticTree.Node>} The function and the remainder of 1429 * the rest list. 1430 * @private 1431 */ 1432cvox.SemanticTree.prototype.getFunctionArgs_ = function(func, rest, heuristic) { 1433 switch (heuristic) { 1434 case 'integral': 1435 var components = this.getIntegralArgs_(rest); 1436 var integrand = this.processRow_(components.integrand); 1437 var funcNode = this.makeIntegralNode_(func, integrand, components.intvar); 1438 components.rest.unshift(funcNode); 1439 return components.rest; 1440 break; 1441 case 'prefix': 1442 if (rest[0] && rest[0].type == cvox.SemanticAttr.Type.FENCED) { 1443 funcNode = this.makeFunctionNode_( 1444 func, /** @type {!cvox.SemanticTree.Node} */ (rest.shift())); 1445 rest.unshift(funcNode); 1446 return rest; 1447 } 1448 case 'bigop': 1449 var partition = cvox.SemanticTree.sliceNodes_( 1450 rest, cvox.SemanticTree.prefixFunctionBoundary_); 1451 var arg = this.processRow_(partition.head); 1452 if (heuristic == 'prefix') { 1453 funcNode = this.makeFunctionNode_(func, arg); 1454 } else { 1455 funcNode = this.makeBigOpNode_(func, arg); 1456 } 1457 if (partition.div) { 1458 partition.tail.unshift(partition.div); 1459 } 1460 partition.tail.unshift(funcNode); 1461 return partition.tail; 1462 break; 1463 case 'simple': 1464 if (rest.length == 0) { 1465 return [func]; 1466 } 1467 var firstArg = rest[0]; 1468 if (firstArg.type == cvox.SemanticAttr.Type.FENCED && 1469 firstArg.role != cvox.SemanticAttr.Role.NEUTRAL && 1470 this.simpleFunctionHeuristic_(firstArg)) { 1471 funcNode = this.makeFunctionNode_( 1472 func, /** @type {!cvox.SemanticTree.Node} */ (rest.shift())); 1473 rest.unshift(funcNode); 1474 return rest; 1475 } 1476 rest.unshift(func); 1477 return rest; 1478 break; 1479 } 1480}; 1481 1482 1483/** 1484 * Tail recursive function to obtain integral arguments. 1485 * @param {!Array.<cvox.SemanticTree.Node>} nodes List of nodes to take 1486 * arguments from. 1487 * @param {Array.<cvox.SemanticTree.Node>=} args List of integral arguments. 1488 * @return {{integrand: !Array.<cvox.SemanticTree.Node>, 1489 * intvar: cvox.SemanticTree.Node, 1490 * rest: !Array.<cvox.SemanticTree.Node>}} 1491 * Result split into integrand, integral variable and the remaining 1492 * elements. 1493 * @private 1494 */ 1495cvox.SemanticTree.prototype.getIntegralArgs_ = function(nodes, args) { 1496 args = args || []; 1497 if (nodes.length == 0) { 1498 return {integrand: args, intvar: null, rest: nodes}; 1499 } 1500 var firstNode = nodes[0]; 1501 if (cvox.SemanticTree.generalFunctionBoundary_(firstNode)) { 1502 return {integrand: args, intvar: null, rest: nodes}; 1503 } 1504 if (cvox.SemanticTree.integralDxBoundarySingle_(firstNode)) { 1505 return {integrand: args, intvar: firstNode, rest: nodes.slice(1)}; 1506 } 1507 if (nodes[1] && cvox.SemanticTree.integralDxBoundary_(firstNode, nodes[1])) { 1508 var comma = this.createNode_(); 1509 comma.updateContent_(cvox.SemanticAttr.invisibleComma()); 1510 var intvar = this.makePunctuatedNode_( 1511 [firstNode, comma, nodes[1]], [comma]); 1512 intvar.role = cvox.SemanticAttr.Role.INTEGRAL; 1513 return {integrand: args, intvar: intvar, rest: nodes.slice(2)}; 1514 } 1515 args.push(nodes.shift()); 1516 return this.getIntegralArgs_(nodes, args); 1517}; 1518 1519 1520/** 1521 * Create a function node. 1522 * @param {!cvox.SemanticTree.Node} func The function operator. 1523 * @param {!cvox.SemanticTree.Node} arg The argument. 1524 * @return {!cvox.SemanticTree.Node} The new function node. 1525 * @private 1526 */ 1527cvox.SemanticTree.prototype.makeFunctionNode_ = function(func, arg) { 1528 var applNode = this.createNode_(); 1529 applNode.updateContent_(cvox.SemanticAttr.functionApplication()); 1530 applNode.type = cvox.SemanticAttr.Type.PUNCTUATION; 1531 applNode.role = cvox.SemanticAttr.Role.APPLICATION; 1532 var newNode = this.makeBranchNode_(cvox.SemanticAttr.Type.APPL, [func, arg], 1533 [applNode]); 1534 newNode.role = func.role; 1535 return newNode; 1536}; 1537 1538 1539/** 1540 * Create a big operator node. 1541 * @param {!cvox.SemanticTree.Node} bigOp The big operator. 1542 * @param {!cvox.SemanticTree.Node} arg The argument. 1543 * @return {!cvox.SemanticTree.Node} The new big operator node. 1544 * @private 1545 */ 1546cvox.SemanticTree.prototype.makeBigOpNode_ = function(bigOp, arg) { 1547 var newNode = this.makeBranchNode_( 1548 cvox.SemanticAttr.Type.BIGOP, [bigOp, arg], []); 1549 newNode.role = bigOp.role; 1550 return newNode; 1551}; 1552 1553 1554/** 1555 * Create an integral node. It has three children: integral, integrand and 1556 * integration variable. The latter two can be omitted. 1557 * @param {!cvox.SemanticTree.Node} integral The integral operator. 1558 * @param {cvox.SemanticTree.Node} integrand The integrand. 1559 * @param {cvox.SemanticTree.Node} intvar The integral variable. 1560 * @return {!cvox.SemanticTree.Node} The new integral node. 1561 * @private 1562 */ 1563cvox.SemanticTree.prototype.makeIntegralNode_ = function( 1564 integral, integrand, intvar) { 1565 integrand = integrand || this.makeEmptyNode_(); 1566 intvar = intvar || this.makeEmptyNode_(); 1567 var newNode = this.makeBranchNode_(cvox.SemanticAttr.Type.INTEGRAL, 1568 [integral, integrand, intvar], []); 1569 newNode.role = integral.role; 1570 return newNode; 1571}; 1572 1573 1574/** 1575 * Predicate implementing the boundary criteria for simple functions: 1576 * 1577 * @param {!cvox.SemanticTree.Node} node A semantic node of type fenced. 1578 * @return {boolean} True if the node meets the boundary criteria. 1579 * @private 1580 */ 1581cvox.SemanticTree.prototype.simpleFunctionHeuristic_ = function(node) { 1582 var children = node.childNodes; 1583 if (children.length == 0) { 1584 return true; 1585 } 1586 if (children.length > 1) { 1587 return false; 1588 } 1589 var child = children[0]; 1590 if (child.type == cvox.SemanticAttr.Type.INFIXOP) { 1591 if (child.role != cvox.SemanticAttr.Role.IMPLICIT) { 1592 return false; 1593 } 1594 if (child.childNodes.some(cvox.SemanticTree.attrPred_('type', 'INFIXOP'))) { 1595 return false; 1596 } 1597 } 1598 return true; 1599}; 1600 1601 1602/** 1603 * Predicate implementing the boundary criteria for prefix functions and big 1604 * operators: 1605 * 1. an explicit operator, 1606 * 2. a relation symbol, or 1607 * 3. some punctuation. 1608 * @param {cvox.SemanticTree.Node} node A semantic node. 1609 * @return {boolean} True if the node meets the boundary criteria. 1610 * @private 1611 */ 1612cvox.SemanticTree.prefixFunctionBoundary_ = function(node) { 1613 return cvox.SemanticTree.attrPred_('type', 'OPERATOR')(node) || 1614 cvox.SemanticTree.generalFunctionBoundary_(node); 1615}; 1616 1617 1618/** 1619 * Predicate implementing the boundary criteria for integrals dx on two nodes. 1620 * @param {cvox.SemanticTree.Node} firstNode A semantic node. 1621 * @param {cvox.SemanticTree.Node} secondNode The direct neighbour of first 1622 * Node. 1623 * @return {boolean} True if the second node exists and the first node is a 'd'. 1624 * @private 1625 */ 1626cvox.SemanticTree.integralDxBoundary_ = function( 1627 firstNode, secondNode) { 1628 return !!secondNode && 1629 cvox.SemanticTree.attrPred_('type', 'IDENTIFIER')(secondNode) && 1630 cvox.SemanticAttr.isCharacterD(firstNode.textContent); 1631}; 1632 1633 1634/** 1635 * Predicate implementing the boundary criteria for integrals dx on a single 1636 * node. 1637 * @param {cvox.SemanticTree.Node} node A semantic node. 1638 * @return {boolean} True if the node meets the boundary criteria. 1639 * @private 1640 */ 1641cvox.SemanticTree.integralDxBoundarySingle_ = function(node) { 1642 if (cvox.SemanticTree.attrPred_('type', 'IDENTIFIER')(node)) { 1643 var firstChar = node.textContent[0]; 1644 return firstChar && node.textContent[1] && 1645 cvox.SemanticAttr.isCharacterD(firstChar); 1646 } 1647 return false; 1648}; 1649 1650 1651/** 1652 * Predicate implementing the general boundary criteria for function operators: 1653 * 1. a relation symbol, 1654 * 2. some punctuation. 1655 * @param {cvox.SemanticTree.Node} node A semantic node. 1656 * @return {boolean} True if the node meets the boundary criteria. 1657 * @private 1658 */ 1659cvox.SemanticTree.generalFunctionBoundary_ = function(node) { 1660 return cvox.SemanticTree.attrPred_('type', 'RELATION')(node) || 1661 cvox.SemanticTree.attrPred_('type', 'PUNCTUATION')(node); 1662}; 1663 1664 1665/** 1666 * Rewrites tables into matrices or case statements in a list of nodes. 1667 * @param {!Array.<cvox.SemanticTree.Node>} nodes List of nodes to rewrite. 1668 * @return {!Array.<cvox.SemanticTree.Node>} The new list of nodes. 1669 * @private 1670 */ 1671cvox.SemanticTree.prototype.processTablesInRow_ = function(nodes) { 1672 // First we process all matrices: 1673 var partition = cvox.SemanticTree.partitionNodes_( 1674 nodes, cvox.SemanticTree.tableIsMatrixOrVector_); 1675 var result = []; 1676 for (var i = 0, matrix; matrix = partition.rel[i]; i++) { 1677 result = result.concat(partition.comp.shift()); 1678 result.push(this.tableToMatrixOrVector_(matrix)); 1679 } 1680 result = result.concat(partition.comp.shift()); 1681 // Process the remaining tables for cases. 1682 partition = cvox.SemanticTree.partitionNodes_( 1683 result, cvox.SemanticTree.isTableOrMultiline_); 1684 result = []; 1685 for (var i = 0, table; table = partition.rel[i]; i++) { 1686 var prevNodes = partition.comp.shift(); 1687 if (cvox.SemanticTree.tableIsCases_(table, prevNodes)) { 1688 this.tableToCases_( 1689 table, /** @type {!cvox.SemanticTree.Node} */ (prevNodes.pop())); 1690 } 1691 result = result.concat(prevNodes); 1692 result.push(table); 1693 } 1694 return result.concat(partition.comp.shift()); 1695}; 1696 1697 1698/** 1699 * Decides if a node is a table or multiline element. 1700 * @param {cvox.SemanticTree.Node} node A node. 1701 * @return {boolean} True if node is either table or multiline. 1702 * @private 1703 */ 1704cvox.SemanticTree.isTableOrMultiline_ = function(node) { 1705 return !!node && (cvox.SemanticTree.attrPred_('type', 'TABLE')(node) || 1706 cvox.SemanticTree.attrPred_('type', 'MULTILINE')(node)); 1707}; 1708 1709 1710/** 1711 * Heuristic to decide if we have a matrix: An expression fenced on both sides 1712 * without any other content is considered a fenced node. 1713 * @param {cvox.SemanticTree.Node} node A node. 1714 * @return {boolean} True if we believe we have a matrix. 1715 * @private 1716 */ 1717cvox.SemanticTree.tableIsMatrixOrVector_ = function(node) { 1718 return !!node && cvox.SemanticTree.attrPred_('type', 'FENCED')(node) && 1719 cvox.SemanticTree.attrPred_('role', 'LEFTRIGHT')(node) && 1720 node.childNodes.length == 1 && 1721 cvox.SemanticTree.isTableOrMultiline_(node.childNodes[0]); 1722}; 1723 1724 1725/** 1726 * Replaces a fenced node by a matrix or vector node. 1727 * @param {!cvox.SemanticTree.Node} node The fenced node to be rewritten. 1728 * @return {!cvox.SemanticTree.Node} The matrix or vector node. 1729 * @private 1730 */ 1731cvox.SemanticTree.prototype.tableToMatrixOrVector_ = function(node) { 1732 var matrix = node.childNodes[0]; 1733 var type = cvox.SemanticTree.attrPred_('type', 'MULTILINE')(matrix) ? 1734 'VECTOR' : 'MATRIX'; 1735 matrix.type = cvox.SemanticAttr.Type[type]; 1736 node.contentNodes.forEach(goog.bind(matrix.appendContentNode_, matrix)); 1737 for (var i = 0, row; row = matrix.childNodes[i]; i++) { 1738 cvox.SemanticTree.assignRoleToRow_(row, cvox.SemanticAttr.Role[type]); 1739 } 1740 return matrix; 1741}; 1742 1743 1744/** 1745 * Heuristic to decide if we have a case statement: An expression with a 1746 * singular open fence before it. 1747 * @param {!cvox.SemanticTree.Node} table A table node. 1748 * @param {!Array.<cvox.SemanticTree.Node>} prevNodes A list of previous nodes. 1749 * @return {boolean} True if we believe we have a case statement. 1750 * @private 1751 */ 1752cvox.SemanticTree.tableIsCases_ = function(table, prevNodes) { 1753 return prevNodes.length > 0 && 1754 cvox.SemanticTree.attrPred_('role', 'OPENFENCE')( 1755 prevNodes[prevNodes.length - 1]); 1756}; 1757 1758 1759/** 1760 * Makes case node out of a table and a fence. 1761 * @param {!cvox.SemanticTree.Node} table The table containing the cases. 1762 * @param {!cvox.SemanticTree.Node} openFence The left delimiter of the case 1763 * statement. 1764 * @return {!cvox.SemanticTree.Node} The cases node. 1765 * @private 1766 */ 1767cvox.SemanticTree.prototype.tableToCases_ = function(table, openFence) { 1768 for (var i = 0, row; row = table.childNodes[i]; i++) { 1769 cvox.SemanticTree.assignRoleToRow_(row, cvox.SemanticAttr.Role.CASES); 1770 // } 1771 } 1772 table.type = cvox.SemanticAttr.Type.CASES; 1773 table.appendContentNode_(openFence); 1774 return table; 1775}; 1776 1777 1778// TODO (sorge) This heuristic is very primitive. We could start reworking 1779// multilines, by combining all cells, semantically rewriting the entire line 1780// and see if there are any similarities. Alternatively, we could look for 1781// similarities in columns (e.g., single relation symbols, like equalities or 1782// inequalities in the same column could indicate an equation array). 1783/** 1784 * Heuristic to decide if we have a multiline formula. A table is considered a 1785 * multiline formula if it does not have any separate cells. 1786 * @param {!cvox.SemanticTree.Node} table A table node. 1787 * @return {boolean} True if we believe we have a mulitline formula. 1788 * @private 1789 */ 1790cvox.SemanticTree.tableIsMultiline_ = function(table) { 1791 return table.childNodes.every( 1792 function(row) { 1793 var length = row.childNodes.length; 1794 return length <= 1;}); 1795}; 1796 1797 1798/** 1799 * Rewrites a table to multiline structure, simplifying it by getting rid of the 1800 * cell hierarchy level. 1801 * @param {!cvox.SemanticTree.Node} table The node to be rewritten a multiline. 1802 * @private 1803 */ 1804cvox.SemanticTree.prototype.tableToMultiline_ = function(table) { 1805 table.type = cvox.SemanticAttr.Type.MULTILINE; 1806 for (var i = 0, row; row = table.childNodes[i]; i++) { 1807 cvox.SemanticTree.rowToLine_(row, cvox.SemanticAttr.Role.MULTILINE); 1808 } 1809}; 1810 1811 1812/** 1813 * Converts a row that only contains one cell into a single line. 1814 * @param {!cvox.SemanticTree.Node} row The row to convert. 1815 * @param {cvox.SemanticAttr.Role=} role The new role for the line. 1816 * @private 1817 */ 1818cvox.SemanticTree.rowToLine_ = function(row, role) { 1819 role = role || cvox.SemanticAttr.Role.UNKNOWN; 1820 if (cvox.SemanticTree.attrPred_('type', 'ROW')(row) && 1821 row.childNodes.length == 1 && 1822 cvox.SemanticTree.attrPred_('type', 'CELL')(row.childNodes[0])) { 1823 row.type = cvox.SemanticAttr.Type.LINE; 1824 row.role = role; 1825 row.childNodes = row.childNodes[0].childNodes; 1826 } 1827}; 1828 1829 1830/** 1831 * Assign a row and its contained cells a new role value. 1832 * @param {!cvox.SemanticTree.Node} row The row to be updated. 1833 * @param {!cvox.SemanticAttr.Role} role The new role for the row and its cells. 1834 * @private 1835 */ 1836cvox.SemanticTree.assignRoleToRow_ = function(row, role) { 1837 if (cvox.SemanticTree.attrPred_('type', 'LINE')(row)) { 1838 row.role = role; 1839 return; 1840 } 1841 if (cvox.SemanticTree.attrPred_('type', 'ROW')(row)) { 1842 row.role = role; 1843 var cellPred = cvox.SemanticTree.attrPred_('type', 'CELL'); 1844 row.childNodes.forEach(function(cell) { 1845 if (cellPred(cell)) { 1846 cell.role = role; 1847 } 1848 }); 1849 } 1850}; 1851 1852 1853/** 1854 * Splits a list of nodes wrt. to a given predicate. 1855 * @param {Array.<cvox.SemanticTree.Node>} nodes A list of nodes. 1856 * @param {!function(cvox.SemanticTree.Node): boolean} pred Predicate for the 1857 * partitioning relation. 1858 * @param {boolean=} reverse If true slicing is done from the end. 1859 * @return {{head: !Array.<cvox.SemanticTree.Node>, 1860 * div: cvox.SemanticTree.Node, 1861 * tail: !Array.<cvox.SemanticTree.Node>}} The split list. 1862 * @private 1863 */ 1864cvox.SemanticTree.sliceNodes_ = function(nodes, pred, reverse) { 1865 if (reverse) { 1866 nodes.reverse(); 1867 } 1868 var head = []; 1869 for (var i = 0, node; node = nodes[i]; i++) { 1870 if (pred(node)) { 1871 if (reverse) { 1872 return {head: nodes.slice(i + 1).reverse(), 1873 div: node, 1874 tail: head.reverse()}; 1875 } 1876 return {head: head, 1877 div: node, 1878 tail: nodes.slice(i + 1)}; 1879 } 1880 head.push(node); 1881 } 1882 if (reverse) { 1883 return {head: [], div: null, tail: head.reverse()}; 1884 } 1885 return {head: head, div: null, tail: []}; 1886}; 1887 1888 1889/** 1890 * Partitions a list of nodes wrt. to a given predicate. Effectively works like 1891 * a PER on the ordered set of nodes. 1892 * @param {!Array.<!cvox.SemanticTree.Node>} nodes A list of nodes. 1893 * @param {!function(cvox.SemanticTree.Node): boolean} pred Predicate for the 1894 * partitioning relation. 1895 * @return {{rel: !Array.<cvox.SemanticTree.Node>, 1896 * comp: !Array.<!Array.<cvox.SemanticTree.Node>>}} 1897 * The partitioning given in terms of a collection of elements satisfying 1898 * the predicate and a collection of complementary sets lying inbetween the 1899 * related elements. Observe that we always have |comp| = |rel| + 1. 1900 * 1901 * Example: On input [a, r_1, b, c, r_2, d, e, r_3] where P(r_i) holds, we 1902 * get as output: {rel: [r_1, r_2, r_3], comp: [[a], [b, c], [d, e], []]. 1903 * @private 1904 */ 1905cvox.SemanticTree.partitionNodes_ = function(nodes, pred) { 1906 var restNodes = nodes; 1907 var rel = []; 1908 var comp = []; 1909 1910 do { 1911 var result = cvox.SemanticTree.sliceNodes_(restNodes, pred); 1912 comp.push(result.head); 1913 rel.push(result.div); 1914 restNodes = result.tail; 1915 } while (result.div); 1916 rel.pop(); 1917 return {rel: rel, comp: comp}; 1918}; 1919 1920 1921/** 1922 * Constructs a predicate to check the semantic attribute of a node. 1923 * @param {!string} prop The property of a node. 1924 * @param {!string} attr The attribute. 1925 * @return {function(cvox.SemanticTree.Node): boolean} The predicate. 1926 * @private 1927 */ 1928 1929cvox.SemanticTree.attrPred_ = function(prop, attr) { 1930 var getAttr = function(prop) { 1931 switch (prop) { 1932 case 'type': return cvox.SemanticAttr.Type[attr]; 1933 case 'role': return cvox.SemanticAttr.Role[attr]; 1934 case 'font': return cvox.SemanticAttr.Font[attr]; 1935 } 1936 }; 1937 1938 return function(node) {return node[prop] == getAttr(prop);}; 1939}; 1940