1 var labelType, useGradients, nativeTextSupport, animate, st, treedata, interactionMethod, 2 wordCount, restOfPhrase, phraseCounter, isEnding, setRootNode=false; 3 4 (function() { 5 var ua = navigator.userAgent, 6 iStuff = ua.match(/iPhone/i) || ua.match(/iPad/i), 7 typeOfCanvas = typeof HTMLCanvasElement, 8 nativeCanvasSupport = (typeOfCanvas == 'object' || typeOfCanvas == 'function'), 9 textSupport = nativeCanvasSupport 10 && (typeof document.createElement('canvas').getContext('2d').fillText == 'function'); 11 12 labelType = (!nativeCanvasSupport || (textSupport && !iStuff))? 'Native' : 'HTML'; 13 nativeTextSupport = labelType == 'Native'; 14 useGradients = nativeCanvasSupport; 15 animate = !(iStuff || !nativeCanvasSupport); 16 })(); 17 18 /** 19 * The Word Tree Log 20 */ 21 var Log = { 22 elem: false, 23 write: function(text) { 24 if (!this.elem) 25 this.elem = document.getElementById('log'); 26 this.elem.innerHTML = text; 27 this.elem.style.left = (700 - this.elem.offsetWidth / 2) + 'px'; 28 } 29 }; 30 31 /** 32 * Initializes the Word Tree: 33 * Sets a duration animation, a transition, the level distance, 34 * the levels to show, navigation and panning, 35 * and defines individual styles of nodes and labels before they 36 * are plotted. 37 */ 38 function initST() { 39 //start with the explore interaction method as default 40 interactionMethod = "explore"; 41 42 //init Wordtree 43 //Create a new ST instance 44 st = new $jit.ST({ 45 'injectInto': 'infovis', 46 //set duration for the animation 47 duration: 400, 48 //set animation transition type 49 transition: $jit.Trans.Quart.easeInOut, 50 //set distance between node and its children 51 levelDistance: 30, 52 //set max levels to show. Useful when used with 53 //the request method for requesting trees of specific depth 54 levelsToShow: 4, 55 //enable panning 56 Navigation: { 57 enable:true, 58 panning:true 59 }, 60 //set node and edge styles 61 //set overridable=true for styling individual 62 //nodes or edges 63 Node: { 64 height: 20, 65 width: 40, 66 //use a custom 67 //node rendering function 68 type: 'nodeline', 69 lineWidth: 2, 70 align:'left', 71 overridable: true 72 }, 73 Edge: { 74 type: 'bezier', 75 lineWidth: 2, 76 color:'#23A4FF', 77 overridable: true 78 }, 79 request: function(nodeId, level, onComplete) { 80 onComplete.onComplete(nodeId); 81 }, 82 onBeforeCompute: function(node) { 83 Log.write("loading " + node.name); 84 }, 85 onAfterCompute: function() { 86 Log.write("done"); 87 }, 88 onCreateLabel: function(label, node) { 89 label.id = node.id; 90 label.innerHTML = node.name; 91 label.onclick = function() { 92 label.innerHTML = node.name; 93 94 switch(interactionMethod) { 95 96 //if the user wants to explore sub-branches of the current word tree 97 case "explore": 98 // only do something if the node has children 99 if (getNumberOfChildren(treedata,node.id) != 0) { 100 //tell the word tree that the node has been clicked 101 //and open the subtrees 102 st.onClick(node.id); 103 //shorten the names of nodes with phrase endings 104 //so that they do not stand in each other's way 105 shortenNames(label,node); 106 107 } else Log.write("end of the phrase"); 108 break; 109 110 //if the user wants to create a new word tree with the clicked node as root 111 case "reroot": 112 //put the new search term into the search-textarea 113 document.theForm.term.value = node.name; 114 //perform the search with the new search value as root 115 search(); 116 break; 117 } 118 }; 119 //compute the size value that is proportional to the 120 //node's frequency's square root 121 var sizeVal = computeSizeVal(frequencies[node.name.toLowerCase()]); 122 123 //set the label styles 124 var style = label.style; 125 var word = node.name; 126 127 //this is necessary so that the labels don't do line breaks 128 style.width = word.length*sizeVal*8; 129 //style.height = (12*sizeVal)+'px'; 130 style.cursor = 'pointer'; 131 style.color = '#fff'; 132 133 //if it's the last word of a phrase make it gray and add a dot 134 if (getNumberOfChildren(treedata,node.id) == 0) { 135 style.color = "#999"; 136 label.innerHTML += "."; 137 } 138 //style.backgroundColor = '#1a1a1a'; 139 style.fontSize = sizeVal+'em'; 140 style.textAlign = 'left'; 141 style.textDecoration = 'none'; 142 style.paddingLeft = '2px'; 143 144 label.$textAlign='left'; 145 146 //check if the node is a unique phrase ending 147 if(getNumberOfChildren(treedata,node.id)==1) { 148 149 //get the rest of the phrase and add it to the label 150 getRestOfPhrase1(treedata,node.id); 151 152 //if it's a unique ending of a phrase 153 if (isEnding) { 154 style.color = '#999'; 155 style.width = (word+restOfPhrase).length*sizeVal*9; 156 node.data.$height = 20; 157 //style.height = '20px'; 158 label.innerHTML += " "+restOfPhrase + "."; 159 style.textAlign = 'left'; 160 style.fontSize = '1em'; 161 162 //remove redundant subtrees 163 st.removeSubtree(node.id, false, 'animate'); 164 165 //this function restores the phrase ending by a user click 166 //if it has been shortened 167 label.onclick = function() { 168 getRestOfPhrase1(treedata,node.id); 169 label.innerHTML = node.name + restOfPhrase + "."; 170 st.onClick(node.id); 171 Log.write("end of the phrase"); 172 }; 173 } 174 175 } 176 177 }, 178 onBeforePlotNode: function(node) { 179 //change the node width to the corresponding word length 180 var sizeVal = computeSizeVal(frequencies[node.name.toLowerCase()]); 181 var word = node.name; 182 node.data.$width = word.length*sizeVal*8; 183 184 getRestOfPhrase1(treedata,node.id); //sets the isEnding boolean 185 186 //only adjust the size if it's no ending 187 if (!isEnding){ 188 node.data.$height= 15*sizeVal; 189 } 190 }, 191 onBeforePlotLine: function(adj) { 192 //highlight the path beween selected nodes 193 if (adj.nodeFrom.selected && adj.nodeTo.selected) { 194 adj.data.$color = "#eed"; 195 adj.data.$lineWidth = 3; 196 } else { 197 delete adj.data.$color; 198 delete adj.data.$lineWidth; 199 } 200 } 201 }); 202 203 /** 204 * Implement a node rendering function called 'nodeline' that plots a straight line 205 * when contracting or expanding a subtree. 206 */ 207 $jit.ST.Plot.NodeTypes.implement({ 208 'nodeline': { 209 'render': function(node, canvas, animating) { 210 if(animating === 'expand' || animating === 'contract') { 211 var pos = node.pos.getc(true), nconfig = this.node, data = node.data; 212 var width = nconfig.width, height = nconfig.height; 213 var algnPos = this.getAlignedPos(pos, width, height); 214 var ctx = canvas.getCtx(), ort = this.config.orientation; 215 ctx.beginPath(); 216 if(ort == 'left' || ort == 'right') { 217 ctx.moveTo(algnPos.x, algnPos.y + height / 2); 218 ctx.lineTo(algnPos.x + width, algnPos.y + height / 2); 219 } else { 220 ctx.moveTo(algnPos.x + width / 2, algnPos.y); 221 ctx.lineTo(algnPos.x + width / 2, algnPos.y + height); 222 } 223 ctx.stroke(); 224 } 225 } 226 } 227 228 }); 229 230 } 231 232 /** 233 * Initializes the JSON Tree structure and loads it into the Word Tree. 234 * Computes the Word Tree, makes a translation and emulates a click on the root node. 235 * Registers Event Handlers for the two interaction methods: explore and reroot. 236 */ 237 function init(json) { 238 //load json data 239 st.loadJSON(eval( '(' + json + ')' )); 240 //compute node positions and layout 241 st.compute(); 242 //make a translation of the tree 243 st.geom.translate(new $jit.Complex(-100, 0), "current"); //"start","current","end" 244 //emulate a click on the root node. 245 st.onClick(st.root); 246 247 //Add event handlers to switch the interaction method 248 function get(id) { 249 return document.getElementById(id); 250 }; 251 252 var explore = get('explore'), reroot = get('reroot'); 253 254 function changeHandler() { 255 if(this.checked) { 256 interactionMethod = this.value; 257 } 258 }; 259 //register changeHandler 260 explore.onchange = reroot.onchange = changeHandler; 261 } 262 263 /** 264 * Search for a term and initialize the corresponding 265 * Word Tree 266 */ 267 function search() { 268 //build the new JSON tree data structure 269 treedata = buildJson(document.theForm.term.value); 270 if(treedata.children.length > 0) { 271 init(JSON.stringify(treedata)); 272 } 273 } 274 275 276 277 var numberOfChildren = -1; 278 /** 279 * Detect the number of children of a clicked node. 280 */ 281 function getNumberOfChildren(node,nodeId) { 282 if (node.id == nodeId) 283 numberOfChildren = node.children.length; 284 else { 285 for (var i in node.children) { 286 getNumberOfChildren(node.children[i],nodeId); 287 } 288 } 289 return numberOfChildren; 290 } 291 292 /** 293 * Computes a size value proportional to the 294 * square root of the node frequency. 295 */ 296 function computeSizeVal(freq){ 297 //adjust the word count so that the font size doesn't get too big or small 298 if (wordCount>500) wordCount = wordCount*0.75; 299 if (wordCount>1000) wordCount = wordCount*0.5; 300 if (wordCount>2000) wordCount = wordCount*0.25; 301 302 //compute the size value 303 var percentage = (freq/wordCount)*100; 304 var sqrt = Math.sqrt(percentage); 305 var freqSize = Math.round(sqrt); 306 if (freqSize==0) freqSize=1; 307 308 return freqSize; 309 } 310 311 /** 312 * A helper function that finds a node in the treedata 313 * and then executes the getRestOfPhrase2 function. 314 */ 315 function getRestOfPhrase1(node,nodeId){ 316 if (node.id == nodeId){ 317 restOfPhrase = ""; 318 phraseCounter = 0; 319 getRestOfPhrase2(node); 320 } 321 else { 322 for (var i in node.children) { 323 getRestOfPhrase1(node.children[i],nodeId); 324 } 325 } 326 } 327 328 /** 329 * Concatenates the rest of the phrase to a string 330 * that has a maximum length of words. 331 */ 332 function getRestOfPhrase2(node){ 333 if (node.children.length == 1) { 334 isEnding = true; 335 restOfPhrase += " "+node.children[0].name; 336 phraseCounter++; 337 if(phraseCounter<14) { 338 getRestOfPhrase2(node.children[0]); 339 } else restOfPhrase += "..."; 340 } 341 else if (node.children.length > 0){ 342 isEnding = false; 343 restOfPhrase = ""; 344 } 345 } 346 347 /** 348 * Shortens the names of the phrase endings 349 * by replacing them with the first word (nodename). 350 */ 351 function shortenNames(label,node){ 352 subnodes = node.getParents()[0].getSubnodes(); 353 for (var i in subnodes){ 354 if ((node._depth == subnodes[i]._depth) && (node.id != subnodes[i].id)){ 355 label = st.labels.getLabel(subnodes[i].id); 356 //alert("Label: "+label.innerHTML); 357 label.innerHTML = subnodes[i].name; 358 } 359 } 360 } 361 362 /** 363 * Choose one of the given speeches 364 */ 365 function chooseText(textName){ 366 document.theForm.inp.value = getText(textName); 367 stDriver(); 368 } 369 370 /** 371 * Get a node object with an ID, 372 * name and frequency. 373 */ 374 function node(name,id) { 375 return { 376 id: name.concat("_").concat(id), 377 name: name, 378 data: {}, 379 frequency:frequencies[name.toString().toLowerCase()], 380 children:[] 381 } 382 } 383 384 /******************************************* 385 * JSON and Word Tree (Suffix Tree) Part * 386 *******************************************/ 387 var trees = new Array(); 388 var sentences = new Array(); 389 var frequencies = {}; 390 var Txt=null, // the input text string 391 root=null, // root of the suffix tree 392 infinity; // quite a big number 393 nForks=0; // number of branching nodes in the suffix tree 394 395 function pair(a, b) { 396 this.fst = a; 397 this.snd = b; 398 } // i.e. <fst, snd> 399 400 function isEmptyStrng() { 401 return this.right < this.left; 402 } 403 404 function Strng(left, right) // represents Txt[left..right] 405 { 406 this.left=left; 407 this.right=right; 408 this.isEmpty = isEmptyStrng; 409 }//constructor 410 411 function addTrnstn(left, right, s) // this['a'] >---(left..right)---> s 412 // add a transition to `this' state 413 { 414 this[Txt[left]] = new pair(new Strng(left,right), s); 415 this.isLeaf = false; 416 } 417 418 function State() // i.e. a new leaf node in the suffix tree 419 { 420 this.addTransition = addTrnstn; 421 this.isLeaf = true; 422 } 423 424 function upDate(s, k, i) 425 // (s, (k, i-1)) is the canonical reference pair for the active point 426 { 427 var oldr = root; 428 var endAndr = test_and_split(s, k, i-1, Txt[i]) 429 var endPoint = endAndr.fst; 430 var r = endAndr.snd 431 432 while (!endPoint) 433 { 434 r.addTransition(i, infinity, new State()); 435 if (oldr != root) 436 oldr.sLink = r; 437 438 oldr = r; 439 var sAndk = canonize(s.sLink, k, i-1) 440 s = sAndk.fst; 441 k = sAndk.snd; 442 endAndr = test_and_split(s, k, i-1, Txt[i]) 443 endPoint = endAndr.fst; 444 r = endAndr.snd; 445 } 446 447 if(oldr != root) 448 oldr.sLink = s; 449 450 return new pair(s, k); 451 }//update 452 453 function test_and_split(s, k, p, t) 454 { 455 if(k<=p) 456 { 457 // find the t_k transition g'(s,(k',p'))=s' from s 458 // k1 is k' p1 is p' 459 var w1ands1 = s[Txt[k]]; // s --(w1)--> s1 460 var s1 = w1ands1.snd; 461 var k1 = w1ands1.fst.left; 462 var p1 = w1ands1.fst.right; 463 464 if (t == Txt[k1 + p - k + 1]) 465 return new pair(true, s); 466 else { 467 var r = new State() 468 s.addTransition(k1, k1+p-k, r); // s ----> r ----> s1 469 r.addTransition( k1+p-k+1, p1, s1); 470 return new pair(false, r) 471 } 472 } else // k > p; ? is there a t-transition from s ? 473 return new pair(s[t] != null, s); 474 }//test_and_split 475 476 function canonize(s, k, p) { 477 if(p < k) 478 return new pair (s, k); 479 480 // find the t_k transition g'(s,(k',p'))=s' from s 481 // k1 is k', p1 is p' 482 var w1ands1 = s[Txt[k]]; // s --(w1)--> s1 483 var s1 = w1ands1.snd; 484 var k1 = w1ands1.fst.left; 485 var p1 = w1ands1.fst.right; 486 487 while(p1-k1 <= p-k) // s --(w1)--> s1 ---> ... 488 { 489 k += p1 - k1 + 1; // remove |w1| chars from front of w 490 s = s1; 491 if(k <= p) { 492 w1ands1 = s[Txt[k]]; // s --(w1)--> s1 493 s1 = w1ands1.snd; 494 k1 = w1ands1.fst.left; 495 p1 = w1ands1.fst.right; 496 } 497 } 498 return new pair(s, k); 499 }//canonize 500 501 function suffixTreeAlgorithm() { 502 var s, k, i; 503 var bt; 504 505 root = new State(); 506 bt = new State(); // bottom 507 508 // Transitions for all possible chars 509 // from bottom to root 510 for (i=0; i<Txt.length; i++) 511 bt.addTransition(i,i, root); 512 513 root.sLink = bt; 514 s=root; 515 k=0; 516 517 for(i=0; i < Txt.length; i++) { 518 var sAndk = upDate(s, k, i); // (s,k) < - upDate(...) 519 s = sAndk.fst; 520 k = sAndk.snd; 521 sAndk = canonize(s, k, i); // (s,k) < - canonize(...) 522 s = sAndk.fst; 523 k = sAndk.snd; 524 } 525 }//suffixTreeAlgorithm 526 527 // ---------------------------------------------------------------------------- 528 529 String.prototype.trim = function() { 530 return this.replace(/^\s+|\s+$/g, ''); 531 }; 532 533 /** 534 * Build the suffix tree 535 */ 536 function stDriver() { 537 Log.write("building the tree"); 538 // document.getElementById('busy').style.display = 'block'; 539 540 frequencies = {}; 541 542 wordCount = 0; //the number of words in the current tree 543 544 splitted = document.theForm.inp.value.split(/[\\.!?;:\\-]+/); 545 for (var i = 0; i < splitted.length && splitted[i].length > 1; i++) { 546 547 root=null; 548 nForks=0; 549 Txt = splitted[i].trim().split(/[\s,]+/); 550 551 for(var j = 0; j<Txt.length;j++) { 552 Txt[j] = Txt[j].trim(); 553 if(frequencies[Txt[j].toLowerCase()] == undefined) { 554 frequencies[Txt[j].toLowerCase()] = 1; 555 wordCount++; 556 } else { 557 frequencies[Txt[j].toLowerCase()] = frequencies[Txt[j].toLowerCase()]+1; 558 wordCount++; 559 } 560 } 561 sentences[i] = Txt; 562 infinity = Txt.length; 563 nForks = 0; 564 565 suffixTreeAlgorithm(); 566 root.index = i; 567 trees[i] = root; 568 } 569 // document.getElementById('submit').disabled = 'disabled'; 570 Log.write("tree built successfully"); 571 572 }//stDriver 573 574 575 576 /** 577 * Build the JSON tree structure that is needed to load 578 * the Word Tree. 579 */ 580 function buildJson(term) { 581 var terms = term.trim().split(/[\s]+/); 582 //create a node for the term 583 var nodeCounter = 0; 584 // var json = node(term,nodeCounter++); 585 586 var wordlist = new Array(); 587 588 for(var i=0; i<trees.length;i++) { 589 if(hasSuffixForAllWords(terms,trees[i])) { 590 var attr = getAttr(terms[terms.length-1],trees[i]); 591 wordlist.push(sentences[trees[i].index].slice(trees[i][attr].fst.left+1, findRightMost(trees[i][attr])+1)); 592 } 593 } 594 595 var json = node(terms[0],nodeCounter++); 596 var currentNode = json; 597 598 for(i = 1;i<terms.length;i++) { 599 childNode = node(terms[i],nodeCounter++); 600 currentNode.children.push(childNode); 601 currentNode = childNode; 602 } 603 604 var temp = currentNode; 605 606 for(i=0;i<wordlist.length;i++) { 607 out: 608 for(var j=0;j<wordlist[i].length;j++) { 609 for(childindex in currentNode.children) { 610 if(currentNode.children[childindex].name.toLowerCase() == wordlist[i][j].toLowerCase()) { 611 currentNode = currentNode.children[childindex]; 612 continue out; 613 } 614 } 615 var child = node(wordlist[i][j],nodeCounter++); 616 currentNode.children.push(child); 617 currentNode = child; 618 } 619 currentNode = temp; 620 } 621 return json; 622 } 623 624 /** 625 * Find the right most pair 626 */ 627 function findRightMost(pair) { 628 if(pair.snd.isLeaf) 629 return pair.fst.right; 630 else { 631 var max = 0; 632 for(attr in pair.snd) { 633 if(attr != "addTransition" && attr != "isLeaf" && attr != "sLink" && attr != "index") { 634 var temp = findRightMost(pair.snd[attr]); 635 if(temp > max) 636 max = temp; 637 } 638 } 639 return max; 640 } 641 } 642 643 function hasSuffixForAllWords(terms,tree) { 644 out: 645 for(var i=0; i<terms.length;i++) { 646 647 for(attr in tree) { 648 if(attr.toString().toLowerCase() == terms[i].toLowerCase()) { 649 continue out; 650 } 651 } 652 return false; 653 } 654 return true; 655 } 656 657 function getAttr(term,tree) { 658 for(attr in tree) { 659 if(attr.toString().toLowerCase() == term.toLowerCase()) { 660 return attr; 661 } 662 } 663 return undefined; 664 } 665 666