etc/jstree/knhx.js

   1 /* The MIT License
   2
   3    Copyright (c) 2008 Genome Research Ltd (GRL).
   4                  2010 Broad Institute
   5
   6    Permission is hereby granted, free of charge, to any person obtaining
   7    a copy of this software and associated documentation files (the
   8    "Software"), to deal in the Software without restriction, including
   9    without limitation the rights to use, copy, modify, merge, publish,
  10    distribute, sublicense, and/or sell copies of the Software, and to
  11    permit persons to whom the Software is furnished to do so, subject to
  12    the following conditions:
  13
  14    The above copyright notice and this permission notice shall be
  15    included in all copies or substantial portions of the Software.
  16
  17    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  21    BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  22    ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  23    CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  24    SOFTWARE.
  25 */
  26
  27 // Author: Heng Li <lh3@sanger.ac.uk>
  28
  29 /*
  30   A phylogenetic tree is parsed into the following Java-like structure:
  31
  32   class Node {
  33         Node parent;  // pointer to the parent node; null if root
  34         Node[] child; // array of pointers to child nodes
  35         String name;  // name of the current node
  36         double d;     // distance to the parent node
  37         bool hl;      // if the node needs to be highlighted
  38         bool hidden;  // if the node and all its desendants are collapsed
  39   };
  40
  41   class Tree {
  42         Node[] node;  // list of nodes in the finishing order (the leftmost leaf is the first and the root the last)
  43         int error;    // errors in parsing: 0x1=missing left parenthesis; 0x2=missing right; 0x4=unpaired brackets
  44         int n_tips;   // number of tips/leaves in the tree
  45   };
  46
  47   The minimal code for plotting/editing a tree in the Newick format is:
  48
  49 <head><!--[if IE]><script src="excanvas.js"></script><![endif]-->
  50 <script language="JavaScript" src="knhx.js"></script></head>
  51 <body onLoad="knhx_init('canvas', 'nhx');">
  52 <textarea id="nhx" rows="20" cols="120" style="font:11px monospace"></textarea>
  53 <canvas id="canvas" width="800" height="100" style="border:1px solid"></canvas>
  54 </body>
  55
  56 */
  57
  58 /********************************************
  59  ****** The New Hampshire format parser *****
  60  ********************************************/
  61
  62 function kn_new_node() { // private method
  63         return {parent:null, child:[], name:"", meta:"", d:-1.0, hl:false, hidden:false};
  64 }
  65
  66 function kn_add_node(str, l, tree, x) // private method
  67 {
  68         var r, beg, end = 0, z;
  69         z = kn_new_node();
  70         for (i = l, beg = l; i < str.length && str.charAt(i) != ',' && str.charAt(i) != ')'; ++i) {
  71                 var c = str.charAt(i);
  72                 if (c == '[') {
  73                         var meta_beg = i;
  74                         if (end == 0) end = i;
  75                         do ++i; while (i < str.length && str.charAt(i) != ']');
  76                         if (i == str.length) {
  77                                 tree.error |= 4;
  78                                 break;
  79                         }
  80                         z.meta = str.substr(meta_beg, i - meta_beg + 1);
  81                 } else if (c == ':') {
  82                         if (end == 0) end = i;
  83                         for (var j = ++i; i < str.length; ++i) {
  84                                 var cc = str.charAt(i);
  85                                 if ((cc < '0' || cc > '9') && cc != 'e' && cc != 'E' && cc != '+' && cc != '-' && cc != '.')
  86                                         break;
  87                         }
  88                         z.d = parseFloat(str.substr(j, i - j));
  89                         --i;
  90                 } else if (c < '!' && c > '~' && end == 0) end = i;
  91         }
  92         if (end == 0) end = i;
  93         if (end > beg) z.name = str.substr(beg, end - beg);
  94         tree.node.push(z);
  95         return i;
  96 }
  97
  98 /* Parse a string in the New Hampshire format and return a pointer to the tree. */
  99 function kn_parse(str)
 100 {
 101         var stack = new Array();
 102         var tree = new Object();
 103         tree.error = tree.n_tips = 0;
 104         tree.node = new Array();
 105         for (var l = 0; l < str.length;) {
 106                 while (l < str.length && (str.charAt(l) < '!' || str.charAt(l) > '~')) ++l;
 107                 if (l == str.length) break;
 108                 var c = str.charAt(l);
 109                 if (c == ',') ++l;
 110                 else if (c == '(') {
 111                         stack.push(-1); ++l;
 112                 } else if (c == ')') {
 113                         var x, m, i;
 114                         x = tree.node.length;
 115                         for (i = stack.length - 1; i >= 0; --i)
 116                                 if (stack[i] < 0) break;
 117                         if (i < 0) {
 118                                 tree.error |= 1; break;
 119                         }
 120                         m = stack.length - 1 - i;
 121                         l = kn_add_node(str, l + 1, tree, m);
 122                         for (i = stack.length - 1, m = m - 1; m >= 0; --m, --i) {
 123                                 tree.node[x].child[m] = tree.node[stack[i]];
 124                                 tree.node[stack[i]].parent = tree.node[x];
 125                         }
 126                         stack.length = i;
 127                         stack.push(x);
 128                 } else {
 129                         ++tree.n_tips;
 130                         stack.push(tree.node.length);
 131                         l = kn_add_node(str, l, tree, 0);
 132                 }
 133         }
 134         if (stack.length > 1) tree.error |= 2;
 135         tree.root = tree.node[tree.node.length - 1];
 136         return tree;
 137 }
 138
 139 /*********************************
 140  ***** Output a tree in text *****
 141  *********************************/
 142
 143 /* convert a tree to the New Hampshire string */
 144 function kn_write_nh(tree)
 145 {
 146         // calculate the depth of each node
 147         tree.node[tree.node.length-1].depth = 0;
 148         for (var i = tree.node.length - 2; i >= 0; --i) {
 149                 var p = tree.node[i];
 150                 p.depth = p.parent.depth + 1;
 151         }
 152         // generate the string
 153         var str = '';
 154         var cur_depth = 0, is_first = 1;
 155         for (var i = 0; i < tree.node.length; ++i) {
 156                 var p = tree.node[i];
 157                 var n_bra = p.depth - cur_depth;
 158                 if (n_bra > 0) {
 159                         if (is_first) is_first = 0;
 160                         else str += ",\n";
 161                         for (var j = 0; j < n_bra; ++j) str += "(";
 162                 } else if (n_bra < 0) str += "\n)";
 163                 else str += ",\n";
 164                 if (p.name) str += String(p.name);
 165                 if (p.d >= 0.0) str += ":" + p.d;
 166                 if (p.meta) str += p.meta;
 167                 cur_depth = p.depth;
 168         }
 169         str += "\n";
 170         return str;
 171 }
 172
 173 /* print the tree topology (for debugging only) */
 174 function kn_check_tree(tree)
 175 {
 176         document.write("<table border=1><tr><th>name<th>id<th>dist<th>x<th>y</tr>");
 177         for (var i = 0; i < tree.node.length; ++i) {
 178                 var p = tree.node[i];
 179                 document.write("<tr>" + "<td>" + p.name + "<td>" + i + "<td>" + p.d
 180                                            + "<td>" + p.x + "<td>" + p.y + "</tr>");
 181         }
 182         document.write("</table>");
 183 }
 184
 185 /**********************************************
 186  ****** Functions for manipulating a tree *****
 187  **********************************************/
 188
 189 /* Expand the tree into an array in the finishing order */
 190 function kn_expand_node(root)
 191 {
 192         var node, stack;
 193         node = new Array();
 194         stack = new Array();
 195         stack.push({p:root, i:0});
 196         for (;;) {
 197                 while (stack[stack.length-1].i != stack[stack.length-1].p.child.length && !stack[stack.length-1].p.hidden) {
 198                         var q = stack[stack.length-1];
 199                         stack.push({p:q.p.child[q.i], i:0});
 200                 }
 201                 node.push(stack.pop().p);
 202                 if (stack.length > 0) ++stack[stack.length-1].i;
 203                 else break;
 204         }
 205         return node;
 206 }
 207
 208 /* Count the number of leaves */
 209 function kn_count_tips(tree)
 210 {
 211         tree.n_tips = 0;
 212         for (var i = 0; i < tree.node.length; ++i)
 213                 if (tree.node[i].child.length == 0 || tree.node[i].hidden)
 214                         ++tree.n_tips;
 215         return tree.n_tips;
 216 }
 217
 218 /* Highlight: set node.hl for leaves matching "pattern" */
 219 function kn_search_leaf(tree, pattern)
 220 {
 221         for (var i = 0; i < tree.node.length; ++i) {
 222                 var p = tree.node[i];
 223                 if (p.child.length == 0)
 224                         p.hl = (pattern && pattern != "" && p.name.match(pattern))? true : false;
 225         }
 226 }
 227
 228 /* Remove: delete a node and all its descendants */
 229 function kn_remove_node(tree, node)
 230 {
 231         var root = tree.node[tree.node.length - 1];
 232         if (node == root) return;
 233
 234         var z = kn_new_node();
 235         z.child.push(root); root.parent = z;
 236
 237         var p = node.parent, i;
 238         if (p.child.length == 2) { // then p will be removed
 239                 var q, r = p.parent;
 240                 i = (p.child[0] == node)? 0 : 1;
 241                 q = p.child[1 - i]; // the other child
 242                 q.d += p.d;
 243                 q.parent = r;
 244                 for (i = 0; i < r.child.length; ++i)
 245                         if (r.child[i] == p) break;
 246                 r.child[i] = q; p.parent = null;
 247         } else {
 248                 var j, k;
 249                 for (i = 0; i < p.child.length; ++i)
 250                         if (p.child[i] == node) break;
 251                 for (j = k = 0; j < p.child.length; ++j) {
 252                         p.node[k] = p.node[j];
 253                         if (j != i) ++k;
 254                 }
 255                 --p.child.length;
 256         }
 257
 258         root = z.child[0];
 259         root.parent = null;
 260         return root;
 261 }
 262
 263 /* Move: prune the subtree descending from p and regragh it to the edge between q and its parent */
 264 function kn_move_node(tree, p, q)
 265 {
 266         var root = tree.node[tree.node.length - 1];
 267         if (p == root) return null; // p cannot be root
 268         for (var r = q; r.parent; r = r.parent)
 269                 if (r == p) return null; // p is an ancestor of q. We cannot move in this case.
 270
 271         root = kn_remove_node(tree, p);
 272
 273         var z = kn_new_node(); // a fake root
 274         z.child.push(root); root.parent = z;
 275
 276         var i, r = q.parent;
 277         for (i = 0; i < r.child.length; ++i)
 278                 if (r.child[i] == q) break;
 279         var s = kn_new_node(); // a new node
 280         s.parent = r; r.child[i] = s;
 281         if (q.d >= 0.0) {
 282                 s.d = q.d / 2.0;
 283                 q.d /= 2.0;
 284         }
 285         s.child.push(p); p.parent = s;
 286         s.child.push(q); q.parent = s;
 287
 288         root = z.child[0];
 289         root.parent = null;
 290         return root;
 291 }
 292
 293 /* Reroot: put the root in the middle of node and its parent */
 294 function kn_reroot(root, node, dist)
 295 {
 296         var i, d, tmp;
 297         var p, q, r, s, new_root;
 298         if (node == root) return root;
 299         if (dist < 0.0 || dist > node.d) dist = node.d / 2.0;
 300         tmp = node.d;
 301
 302         /* p: the central multi-parent node
 303          * q: the new parent, previous a child of p
 304          * r: old parent
 305          * i: previous position of q in p
 306          * d: previous distance p->d
 307          */
 308         q = new_root = kn_new_node();
 309         q.child[0] = node;
 310         q.child[0].d = dist;
 311         p = node.parent;
 312         q.child[0].parent = q;
 313         for (i = 0; i < p.child.length; ++i)
 314                 if (p.child[i] == node) break;
 315         q.child[1] = p;
 316         d = p.d;
 317         p.d = tmp - dist;
 318         r = p.parent;
 319         p.parent = q;
 320         while (r != null) {
 321                 s = r.parent; /* store r's parent */
 322                 p.child[i] = r; /* change r to p's child */
 323                 for (i = 0; i < r.child.length; ++i) /* update i */
 324                         if (r.child[i] == p) break;
 325                 r.parent = p; /* update r's parent */
 326                 tmp = r.d; r.d = d; d = tmp; /* swap r->d and d, i.e. update r->d */
 327                 q = p; p = r; r = s; /* update p, q and r */
 328         }
 329         /* now p is the root node */
 330         if (p.child.length == 2) { /* remove p and link the other child of p to q */
 331                 r = p.child[1 - i]; /* get the other child */
 332                 for (i = 0; i < q.child.length; ++i) /* the position of p in q */
 333                         if (q.child[i] == p) break;
 334                 r.d += p.d;
 335                 r.parent = q;
 336                 q.child[i] = r; /* link r to q */
 337         } else { /* remove one child in p */
 338                 for (j = k = 0; j < p.child.length; ++j) {
 339                         p.child[k] = p.child[j];
 340                         if (j != i) ++k;
 341                 }
 342                 --p.child.length;
 343         }
 344         return new_root;
 345 }
 346
 347 function kn_multifurcate(p)
 348 {
 349         var i, par, idx, tmp, old_length;
 350         if (p.child.length == 0 || !p.parent) return;
 351         par = p.parent;
 352         for (i = 0; i < par.child.length; ++i)
 353                 if (par.child[i] == p) break;
 354         idx = i; tmp = par.child.length - idx - 1;
 355         old_length = par.child.length;
 356         par.child.length += p.child.length - 1;
 357         for (i = 0; i < tmp; ++i)
 358                 par.child[par.child.length - 1 - i] = par.child[old_length - 1 - i];
 359         for (i = 0; i < p.child.length; ++i) {
 360                 p.child[i].parent = par;
 361                 if (p.child[i].d >= 0 && p.d >= 0) p.child[i].d += p.d;
 362                 par.child[i + idx] = p.child[i];
 363         }
 364 }
 365
 366 function kn_reorder(root)
 367 {
 368         sort_leaf = function(a, b) {
 369                 if (a.depth < b.depth) return 1;
 370                 if (a.depth > b.depth) return -1;
 371                 return String(a.name) < String(b.name)? -1 : String(a.name) > String(b.name)? 1 : 0;
 372         };
 373         sort_weight = function(a, b) { return a.weight / a.n_tips - b.weight / b.n_tips; };
 374
 375         var x = new Array();
 376         var i, node = kn_expand_node(root);
 377         // get depth
 378         node[node.length-1].depth = 0;
 379         for (i = node.length - 2; i >= 0; --i) {
 380                 var q = node[i];
 381                 q.depth = q.parent.depth + 1;
 382                 if (q.child.length == 0) x.push(q);
 383         }
 384         // set weight for leaves
 385         x.sort(sort_leaf);
 386         for (i = 0; i < x.length; ++i) x[i].weight = i, x[i].n_tips = 1;
 387         // set weight for internal nodes
 388         for (i = 0; i < node.length; ++i) {
 389                 var q = node[i];
 390                 if (q.child.length) { // internal
 391                         var j, n = 0, w = 0;
 392                         for (j = 0; j < q.child.length; ++j) {
 393                                 n += q.child[j].n_tips;
 394                                 w += q.child[j].weight;
 395                         }
 396                         q.n_tips = n; q.weight = w;
 397                 }
 398         }
 399         // swap children
 400         for (i = 0; i < node.length; ++i)
 401                 if (node[i].child.length >= 2)
 402                         node[i].child.sort(sort_weight);
 403 }
 404
 405 /*****************************************
 406  ***** Functions for plotting a tree *****
 407  *****************************************/
 408
 409 /* Calculate the coordinate of each node */
 410 function kn_calxy(tree, is_real)
 411 {
 412         var i, j, scale;
 413         // calculate y
 414         scale = tree.n_tips - 1;
 415         for (i = j = 0; i < tree.node.length; ++i) {
 416                 var p = tree.node[i];
 417                 p.y = (p.child.length && !p.hidden)? (p.child[0].y + p.child[p.child.length-1].y) / 2.0 : (j++) / scale;
 418                 if (p.child.length == 0) p.miny = p.maxy = p.y;
 419                 else p.miny = p.child[0].miny, p.maxy = p.child[p.child.length-1].maxy;
 420         }
 421         // calculate x
 422         if (is_real) { // use branch length
 423                 var root = tree.node[tree.node.length-1];
 424                 scale = root.x = (root.d >= 0.0)? root.d : 0.0;
 425                 for (i = tree.node.length - 2; i >= 0; --i) {
 426                         var p = tree.node[i];
 427                         p.x = p.parent.x + (p.d >= 0.0? p.d : 0.0);
 428                         if (p.x > scale) scale = p.x;
 429                 }
 430                 if (scale == 0.0) is_real = false;
 431         }
 432         if (!is_real) { // no branch length
 433                 scale = tree.node[tree.node.length-1].x = 1.0;
 434                 for (i = tree.node.length - 2; i >= 0; --i) {
 435                         var p = tree.node[i];
 436                         p.x = p.parent.x + 1.0;
 437                         if (p.x > scale) scale = p.x;
 438                 }
 439                 for (i = 0; i < tree.node.length - 1; ++i)
 440                         if (tree.node[i].child.length == 0)
 441                                 tree.node[i].x = scale;
 442         }
 443         // rescale x
 444         for (i = 0; i < tree.node.length; ++i)
 445                 tree.node[i].x /= scale;
 446         return is_real;
 447 }
 448
 449 function kn_get_node(tree, conf, x, y)
 450 {
 451         if (conf.is_circular) {
 452                 for (var i = 0; i < tree.node.length; ++i) {
 453                         var p = tree.node[i];
 454                         var tmp_x = Math.floor(conf.width/2 + p.x * conf.real_r * Math.cos(p.y * conf.full_arc) + .999);
 455                         var tmp_y = Math.floor(conf.height/2 + p.x * conf.real_r * Math.sin(p.y * conf.full_arc) + .999);
 456                         var tmp_l = 2;
 457                         if (x >= tmp_x - tmp_l && x <= tmp_x + tmp_l && y >= tmp_y - tmp_l && y <= tmp_y + tmp_l)
 458                                 return i;
 459                 }
 460         } else {
 461                 for (var i = 0; i < tree.node.length; ++i) {
 462                         var tmp_x = tree.node[i].x * conf.real_x + conf.shift_x;
 463                         var tmp_y = tree.node[i].y * conf.real_y + conf.shift_y;
 464                         var tmp_l = conf.box_width * .6;
 465                         if (x >= tmp_x - tmp_l && x <= tmp_x + tmp_l && y >= tmp_y - tmp_l && y <= tmp_y + tmp_l)
 466                                 return i;
 467                 }
 468         }
 469         return tree.node.length;
 470 }
 471
 472 /* Initialize parameters for tree plotting */
 473 function kn_init_conf()
 474 {
 475         var conf = new Object();
 476         conf.c_box = new Array();
 477         conf.width = 800; conf.height = 600;
 478         conf.xmargin = 20; conf.ymargin = 20;
 479         conf.fontsize = 8;
 480         conf.font = "Helvetica";
 481         conf.c_ext = "rgb(0,0,0)";
 482         conf.c_int = "rgb(255,0,0)";
 483         conf.c_line = "rgb(0,20,200)";
 484         conf.c_node = "rgb(0,20,200)";
 485         conf.c_dup = "rgb(255,0,0)";
 486         conf.c_active_node = "rgb(255,128,0)"
 487         conf.c_hl = "rgb(255, 180, 180)";
 488         conf.c_hidden = "rgb(0,200,0)";
 489         conf.c_regex = "rgb(0,128,0)";
 490 //      conf.regex = ':S=([^:\\]]+)';
 491         conf.regex = ':B=([^:\\]]+)';
 492         conf.xskip = 3.0;
 493         conf.yskip = 14;
 494         conf.box_width = 6.0;
 495         conf.old_nh = null;
 496         conf.is_real = true;
 497         conf.is_circular = false;
 498         conf.show_dup = true;
 499         conf.runtime = 0;
 500         return conf;
 501 }
 502
 503 /* Plot the tree in the "canvas". Both node.x and node.y MUST BE precomputed by kn_calxy */
 504 function kn_plot_core(canvas, tree, conf)
 505 {
 506         if (conf.is_circular) {
 507                 kn_plot_core_O(canvas, tree, conf);
 508                 return;
 509         }
 510         var ctx = canvas.getContext("2d");
 511 //      ctx.font = "10px Sans";
 512         ctx.font = conf.fontsize*1.25 + 'px ' + conf.font;
 513         ctx.strokeStyle = ctx.fillStyle = "white";
 514         ctx.fillRect(0, 0, conf.width, conf.height);
 515         CanvasTextFunctions.enable(ctx);
 516         // get maximum name length
 517         var max_namelen, i;
 518         for (i = 0, max_namelen = 0; i < tree.node.length; ++i) {
 519                 if (tree.node[i].child.length) continue;
 520                 //var tmp = ctx.CmeasureText(conf.font, conf.fontsize, tree.node[i].name);
 521                 var tmp = ctx.measureText(tree.node[i].name).width;
 522                 if (tmp > max_namelen) max_namelen = tmp;
 523         }
 524         // set transformation
 525         var real_x, real_y, shift_x, shift_y;
 526         conf.real_x = real_x = conf.width - 2 * conf.xmargin - max_namelen;
 527         conf.real_y = real_y = conf.height - 2 * conf.ymargin - conf.fontsize;
 528         conf.shift_x = shift_x = conf.xmargin;
 529         conf.shift_y = shift_y = conf.ymargin + conf.fontsize / 2;
 530         // plot background boxes
 531         for (i = tree.node.length - 1; i >= 0 ; --i) {
 532                 if (tree.node[i].box) {
 533                         var p = tree.node[i];
 534                         var x = p.x * real_x + shift_x - conf.box_width/2;
 535                         ctx.strokeStyle = ctx.fillStyle = tree.node[i].box;
 536                         ctx.fillRect(x, p.miny * real_y + shift_y - conf.yskip/2,
 537                                                  conf.width - conf.xmargin - x, (p.maxy - p.miny) * real_y + conf.yskip);
 538                 }
 539         }
 540         // leaf name
 541         ctx.strokeStyle = conf.c_ext;
 542         ctx.fillStyle = conf.c_ext;
 543         for (i = 0; i < tree.node.length; ++i) {
 544                 var p = tree.node[i];
 545                 if (p.child.length == 0 || p.hidden) {
 546                         if (p.hl) {
 547                                 //var tmp = ctx.CmeasureText(conf.font, conf.fontsize, tree.node[i].name);
 548                                 var tmp = ctx.measureText(tree.node[i].name).width;
 549                                 ctx.fillRect(p.x * real_x + conf.xskip * 2 + shift_x, p.y * real_y + shift_y - conf.fontsize * .8,
 550                                                          tmp, conf.fontsize * 1.5);
 551                         }
 552                         ctx.fillText(p.name, p.x * real_x + conf.xskip * 2 + shift_x, p.y * real_y + shift_y + conf.fontsize / 3);
 553 //                      ctx.drawText(conf.font, conf.fontsize, p.x * real_x + conf.xskip * 2 + shift_x,
 554 //                                               p.y * real_y + shift_y + conf.fontsize / 3, p.name);
 555                 }
 556         }
 557         // internal name
 558         ctx.textAlign="right";
 559         ctx.strokeStyle = conf.c_int;
 560         ctx.fillStyle = conf.c_int;
 561         for (i = 0; i < tree.node.length; ++i) {
 562                 var p = tree.node[i];
 563                 if (p.child.length && p.name.length > 0 && !p.hidden) {
 564                         ctx.fillText(p.name, p.x * real_x - conf.xskip + shift_x, p.y * real_y + shift_y - conf.fontsize / 3);
 565 //                      var l = ctx.CmeasureText(conf.font, conf.fontsize, p.name);
 566 //                      ctx.drawText(conf.font, conf.fontsize, p.x * real_x - conf.xskip + shift_x - l,
 567 //                                               p.y * real_y + shift_y - conf.fontsize / 3, p.name);
 568                 }
 569         }
 570         // internal name 2
 571         if (conf.regex && conf.regex.indexOf('(') >= 0) {
 572                 var re = new RegExp(conf.regex);
 573                 if (re) {
 574                         ctx.strokeStyle = conf.c_regex;
 575                         ctx.fillStyle = conf.c_regex;
 576                         for (i = 0; i < tree.node.length; ++i) {
 577                                 var p = tree.node[i];
 578                                 if (p.meta) {
 579                                         var m = re.exec(p.meta);
 580                                         if (m && m.length > 1) {        // m may be null, thus test itself first !
 581                                                 ctx.fillText(m[1], p.x * real_x - conf.xskip + shift_x, p.y * real_y + shift_y + conf.fontsize * 1.33);
 582 //                                              var l = ctx.CmeasureText(conf.font, conf.fontsize, m[1]);
 583 //                                              ctx.drawText(conf.font, conf.fontsize, p.x * real_x - conf.xskip + shift_x - l,
 584 //                                                                       p.y * real_y + shift_y + conf.fontsize * 1.33, m[1]);
 585                                         }
 586                                 }
 587                         }
 588                 }
 589         }
 590         ctx.textAlign="left";   // restore default
 591         // horizontal lines
 592         var y;
 593         ctx.strokeStyle = conf.c_line;
 594         ctx.beginPath();
 595         y = tree.node[tree.node.length-1].y * real_y + shift_y;
 596         ctx.moveTo(shift_x, y); ctx.lineTo(tree.node[tree.node.length-1].x * real_x + shift_x, y);
 597         for (i = 0; i < tree.node.length - 1; ++i) {
 598                 var p = tree.node[i];
 599                 y = p.y * real_y + shift_y;
 600                 ctx.moveTo(p.parent.x * real_x + shift_x, y);
 601                 ctx.lineTo(p.x * real_x + shift_x, y);
 602         }
 603         // vertical lines
 604         var x;
 605         for (i = 0; i < tree.node.length; ++i) {
 606                 var p = tree.node[i];
 607                 if (p.child.length == 0 || p.hidden) continue;
 608                 x = p.x * real_x + shift_x;
 609                 ctx.moveTo(x, p.child[0].y * real_y + shift_y);
 610                 ctx.lineTo(x, p.child[p.child.length-1].y * real_y + shift_y);
 611         }
 612         ctx.stroke();
 613         ctx.closePath();
 614         // nodes
 615         for (i = 0; i < tree.node.length; ++i) {
 616                 var tmp_x, tmp_y, tmp_l;
 617                 var p = tree.node[i];
 618                 tmp_x = p.x * real_x + shift_x;
 619                 tmp_y = p.y * real_y + shift_y;
 620                 tmp_l = conf.box_width / 2;
 621                 if (p.hidden) ctx.fillStyle = conf.c_hidden;
 622                 else if (conf.show_dup && /:D=Y/i.test(p.meta)) ctx.fillStyle = conf.c_dup;
 623                 else ctx.fillStyle = conf.c_node;
 624                 ctx.fillRect(tmp_x - tmp_l, tmp_y - tmp_l, conf.box_width, conf.box_width);
 625         }
 626 }
 627
 628 function kn_plot_core_O(canvas, tree, conf)
 629 {
 630         var ctx = canvas.getContext("2d");
 631         ctx.strokeStyle = ctx.fillStyle = "white";
 632         ctx.fillRect(0, 0, conf.width, conf.height);
 633         CanvasTextFunctions.enable(ctx);
 634         // get the maximum name length
 635         var max_namelen, i;
 636         for (i = 0, max_namelen = max_namechr = 0; i < tree.node.length; ++i) {
 637                 if (tree.node[i].child.length) continue;
 638                 var tmp = ctx.CmeasureText(conf.font, conf.fontsize, tree.node[i].name);
 639                 if (tmp > max_namelen) max_namelen = tmp;
 640         }
 641         // set transformation and estimate the font size
 642         var real_r, full = 2 * Math.PI * (350/360), fontsize;
 643         fontsize = (conf.width/2 - conf.xmargin - 1 * tree.n_tips / full) / (max_namelen / conf.fontsize + tree.n_tips / full);
 644         if (fontsize > conf.fontsize) fontsize = conf.fontsize;
 645         max_namelen *= fontsize / conf.fontsize;
 646         conf.real_r = real_r = conf.width/2 - conf.xmargin - max_namelen;
 647         conf.full_arc = full;
 648         ctx.save();
 649         ctx.translate(conf.width/2, conf.height/2);
 650         // plot background boxes
 651         for (i = tree.node.length - 1; i >= 0 ; --i) {
 652                 if (tree.node[i].box) {
 653                         var p = tree.node[i];
 654                         var x = (p.parent? (p.parent.x + p.x)/2 : 0) * real_r;
 655                         var miny, maxy;
 656                         ctx.strokeStyle = ctx.fillStyle = tree.node[i].box;
 657                         ctx.beginPath();
 658                         miny = p.miny - 1. / tree.n_tips / 2;
 659                         maxy = p.maxy + 1. / tree.n_tips / 2;
 660                         ctx.moveTo(x * Math.cos(miny * full), x * Math.sin(miny * full));
 661                         ctx.arc(0, 0, x, miny * full, maxy * full, false);
 662                         ctx.lineTo(x * Math.cos(maxy * full), x * Math.sin(maxy * full));
 663                         ctx.arc(0, 0, real_r, maxy * full, miny * full, true);
 664                         ctx.closePath();
 665                         ctx.fill();
 666                 }
 667         }
 668         // leaf names
 669         ctx.strokeStyle = conf.c_ext;
 670         ctx.fillStyle = conf.c_hl;
 671         for (i = 0; i < tree.node.length; ++i) {
 672                 var p = tree.node[i];
 673                 if (p.child.length) continue;
 674                 ctx.save();
 675                 var tmp;
 676                 if (p.hl) tmp = ctx.CmeasureText(conf.font, fontsize, tree.node[i].name);
 677                 if (p.y * full > Math.PI * .5 && p.y * full < Math.PI * 1.5) {
 678                         ctx.rotate(p.y * full - Math.PI);
 679                         if (p.hl) ctx.fillRect(-(real_r + fontsize/2), -fontsize * .8, -tmp, fontsize * 1.5);
 680                         ctx.drawTextRight(conf.font, fontsize, -(real_r + fontsize/2), fontsize/3, p.name);
 681                 } else {
 682                         ctx.rotate(p.y * full);
 683                         if (p.hl) ctx.fillRect(real_r + fontsize/2, -fontsize * .8, tmp, fontsize * 1.5);
 684                         ctx.drawText(conf.font, fontsize, real_r + fontsize/2, fontsize/3, p.name);
 685                 }
 686                 ctx.restore();
 687         }
 688         // straight lines
 689         ctx.strokeStyle = "black";
 690         ctx.beginPath();
 691         var root = tree.node[tree.node.length-1];
 692         ctx.moveTo(0, 0);
 693         ctx.lineTo(root.x * real_r * Math.cos(root.y * full), root.x * real_r * Math.sin(root.y * full));
 694         for (i = 0; i < tree.node.length - 1; ++i) {
 695                 var p = tree.node[i];
 696                 var cos = Math.cos(p.y * full), sin = Math.sin(p.y * full);
 697                 ctx.moveTo(p.parent.x * real_r * cos, p.parent.x * real_r * sin);
 698                 ctx.lineTo(p.x * real_r * cos, p.x * real_r * sin);
 699         }
 700         ctx.stroke();
 701         ctx.closePath();
 702         // lines towards the tips
 703         ctx.strokeStyle = "lightgray";
 704         ctx.beginPath();
 705         for (i = 0; i < tree.node.length - 1; ++i) {
 706                 var p = tree.node[i];
 707                 if (p.child.length) continue;
 708                 var cos = Math.cos(p.y * full), sin = Math.sin(p.y * full);
 709                 ctx.moveTo(p.x * real_r * cos, p.x * real_r * sin);
 710                 ctx.lineTo(real_r * cos, real_r * sin);
 711         }
 712         ctx.stroke();
 713         ctx.closePath();
 714         // arcs
 715         ctx.strokeStyle = "black";
 716         ctx.beginPath();
 717         for (i = 0; i < tree.node.length; ++i) {
 718                 var p = tree.node[i];
 719                 if (p.child.length == 0 || p.hidden) continue;
 720                 var r = p.x * real_r;
 721                 ctx.moveTo(r * Math.cos(p.child[0].y * full), r * Math.sin(p.child[0].y * full));
 722                 ctx.arc(0, 0, r, p.child[0].y * full, p.child[p.child.length-1].y * full, false); // arcTo is preferred, but may have compatibility issues.
 723         }
 724         ctx.stroke();
 725         ctx.closePath();
 726         ctx.restore();
 727 }
 728
 729 /* Plot the tree "str" in the Newick format in the "canvas" */
 730 function kn_plot_str(canvas, str, conf)
 731 {
 732         var tree = kn_parse(str);
 733         if (tree.error) return tree;
 734         conf.is_real = kn_calxy(tree, conf.is_real);
 735         conf.height = conf.is_circular? conf.width : conf.ymargin * 2 + tree.n_tips * conf.yskip;
 736         canvas.width = conf.width;
 737         canvas.height = conf.height;
 738         kn_plot_core(canvas, tree, conf);
 739         return tree;
 740 }
 741
 742
 743 /******************************************************************
 744  ******************************************************************
 745  ***** The library ends here. The following are DOM specific. *****
 746  ******************************************************************
 747  ******************************************************************/
 748
 749 var kn_g_tree = null;
 750 var kn_g_conf = kn_init_conf();
 751
 752 document.write('<script language="JavaScript" src="menu.js"></script>');
 753 document.write('<script language="JavaScript" src="canvastext.js"></script>');
 754 document.write('<style type="text/css"><!-- \
 755         #popdiv a.alt { \
 756           padding-left: 9px; \
 757           font: 12px monospace; \
 758           border: none; \
 759           display: inline; \
 760         } \
 761 --></style>');
 762
 763 /*****************
 764  * Event handler *
 765  *****************/
 766
 767 kn_actions = new function() {
 768
 769         var id, canvas, textarea;
 770
 771         this.init = function(c, t) { canvas = c; textarea = t; }
 772
 773         this.set_id = function(_id) { id = _id; }
 774
 775         this.init = function(c, t) { canvas = c; textarea = t; }
 776
 777         this.plot = function(str) {
 778                 var time_beg = new Date().getTime();
 779                 if (str) {
 780                         var tree = kn_plot_str(canvas, str, kn_g_conf);
 781                         if (tree.error & 1) alert("Parsing ERROR: missing left parenthesis!");
 782                         else if (tree.error & 2) alert("Parsing ERROR: missing right parenthesis!");
 783                         else if (tree.error & 4) alert("Parsing ERROR: missing brackets!");
 784                         kn_g_tree = tree;
 785                 } else kn_plot_core(canvas, kn_g_tree, kn_g_conf);
 786                 kn_g_conf.runtime = (new Date().getTime() - time_beg)/1000.0;
 787         }
 788
 789         this.plot_str = function() { this.plot(textarea.value); }
 790
 791         this.undo_redo = function() {
 792                 var tmp = kn_g_conf.old_nh; kn_g_conf.old_nh = textarea.value; textarea.value = tmp;
 793                 kn_g_tree = kn_parse(textarea.value);
 794                 kn_g_conf.is_real = kn_calxy(kn_g_tree, kn_g_conf.is_real);
 795                 kn_plot_core(canvas, kn_g_tree, kn_g_conf);
 796         }
 797
 798         var set_undo = function(conf, str) {
 799                 conf.old_nh = textarea.value;
 800                 textarea.value = str;
 801         }
 802
 803         this.get = function(x, y) {
 804                 var id = kn_get_node(kn_g_tree, kn_g_conf, x, y);
 805                 return (id >= 0 && id < kn_g_tree.node.length)? id : -1;
 806         }
 807
 808         this.swap = function() {
 809                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 810                 if (i < tree.node.length && tree.node[i].child.length) {
 811                         var p = tree.node[i];
 812                         var q = p.child[0];
 813                         for (j = 0; j < p.child.length-1; ++j)
 814                                 p.child[j] = p.child[j+1];
 815                         p.child[p.child.length-1] = q;
 816                         tree.node = kn_expand_node(tree.node[tree.node.length-1]);
 817                         conf.is_real = kn_calxy(tree, conf.is_real);
 818                         kn_g_tree = tree; kn_g_conf = conf;
 819                         kn_plot_core(canvas, tree, conf);
 820                         set_undo(conf, kn_write_nh(tree));
 821                 }
 822         }
 823
 824         this.sort = function() {
 825                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 826                 if (i < tree.node.length && tree.node[i].child.length) {
 827                         kn_reorder(tree.node[i]);
 828                         tree.node = kn_expand_node(tree.node[tree.node.length-1]);
 829                         conf.is_real = kn_calxy(tree, conf.is_real);
 830                         kn_g_tree = tree; kn_g_conf = conf;
 831                         kn_plot_core(canvas, tree, conf);
 832                         set_undo(conf, kn_write_nh(tree));
 833                 }
 834         }
 835
 836         this.reroot = function() {
 837                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 838                 if (i < tree.node.length) {
 839                         var new_root = kn_reroot(tree.node[tree.node.length-1], tree.node[i], -1.0);
 840                         tree.node = kn_expand_node(new_root);
 841                         kn_g_tree = tree;
 842                         conf.is_real = kn_calxy(tree, conf.is_real);
 843                         kn_plot_core(canvas, tree, conf);
 844                         set_undo(conf, kn_write_nh(tree));
 845                 }
 846         }
 847
 848         this.collapse = function() {
 849                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 850                 if (i < tree.node.length && tree.node[i].child.length) {
 851                         tree.node[i].hidden = !tree.node[i].hidden;
 852                         var nn = tree.node.length;
 853                         tree.node = kn_expand_node(tree.node[tree.node.length-1]);
 854                         kn_count_tips(tree);
 855                         conf.is_real = kn_calxy(tree, conf.is_real);
 856                         kn_g_tree = tree; kn_g_conf = conf;
 857                         kn_plot_core(canvas, tree, conf);
 858                 }
 859         }
 860
 861         this.remove = function() {
 862                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 863                 if (i < tree.node.length) {
 864                         var new_root = kn_remove_node(tree, tree.node[i]);
 865                         tree.node = kn_expand_node(new_root);
 866                         kn_count_tips(tree);
 867                         kn_g_tree = tree;
 868                         conf.is_real = kn_calxy(tree, conf.is_real);
 869                         kn_plot_core(canvas, tree, conf);
 870                         set_undo(conf, kn_write_nh(tree));
 871 //                      document.getElementById("n_leaves").innerHTML = "#leaves: "+tree.n_tips+";";
 872                 }
 873         }
 874
 875         this.multifurcate = function() {
 876                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 877                 if (i < tree.node.length && tree.node[i].child.length) {
 878                         kn_multifurcate(tree.node[i]);
 879                         tree.node = kn_expand_node(tree.node[tree.node.length-1]);
 880                         conf.is_real = kn_calxy(tree, conf.is_real);
 881                         kn_g_tree = tree; kn_g_conf = conf;
 882                         kn_plot_core(canvas, tree, conf);
 883                         set_undo(conf, kn_write_nh(tree));
 884                 }
 885         }
 886
 887         function move_clear_mark(tree, conf) {
 888                 if (tree.active_node != null && tree.active_node < tree.node.length) {
 889                         var p = tree.node[tree.active_node];
 890                         tree.active_node = null;
 891                         var ctx = canvas.getContext("2d");
 892                         ctx.fillStyle = (conf.show_dup && /:D=Y/i.test(p.meta))? conf.c_dup : conf.c_node;
 893                         ctx.fillRect(p.x * conf.real_x + conf.shift_x - conf.box_width/2,
 894                                                  p.y * conf.real_y + conf.shift_y - conf.box_width/2, conf.box_width, conf.box_width);
 895                 }
 896         }
 897
 898         this.move = function() {
 899                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 900                 if (i < tree.node.length) {
 901                         if (tree.active_node != null && tree.active_node < tree.node.length) {
 902                                 //alert(tree.active_node + " -> " + i);
 903                                 if (tree.node[tree.active_node].parent == tree.node[i]) {
 904                                         alert("Error: cannot move a child to its parent!");
 905                                 } else {
 906                                         var new_root = kn_move_node(tree, tree.node[tree.active_node], tree.node[i]);
 907                                         if (new_root) {
 908                                                 tree.node = kn_expand_node(new_root);
 909                                                 kn_g_tree = tree;
 910                                                 conf.is_real = kn_calxy(tree, conf.is_real);
 911                                                 kn_plot_core(canvas, tree, conf);
 912                                                 set_undo(conf, kn_write_nh(tree));
 913                                         } else alert("Error: Invalid move!");
 914                                 }
 915                                 move_clear_mark(tree, conf);
 916                         } else {
 917                                 tree.active_node = i;
 918                                 var p = tree.node[i];
 919                                 var tmp = conf.box_width - 2;
 920                                 var ctx = canvas.getContext("2d");
 921                                 ctx.fillStyle = conf.c_active_node;
 922                                 ctx.fillRect(p.x * conf.real_x + conf.shift_x - tmp/2,
 923                                                          p.y * conf.real_y + conf.shift_y - tmp/2, tmp, tmp);
 924                         }
 925                 } else move_clear_mark(tree, conf);
 926         }
 927
 928         this.highlight = function(color) {
 929                 var tree = kn_g_tree, conf = kn_g_conf, i = id;
 930                 var lookup = { white : '#FFFFFF', red : '#FFD8D0', green : '#D8FFC0', blue : '#C0D8FF',
 931                                            yellow : '#FFFFC8', pink : '#FFD8FF', cyan : '#D8FFFF', none : 'none' };
 932                 if (lookup[color]) color = lookup[color];
 933                 if (i < tree.node.length) {
 934                         // mark the clade to be highlighted
 935                         var time_beg = new Date().getTime();
 936                         var c = color;
 937                         if (c == 'none') c = null;
 938                         if (c != tree.node[i].box) {
 939                                 tree.node[i].box = c;
 940                                 kn_g_tree = tree; kn_g_conf = conf;
 941                                 kn_plot_core(canvas, tree, conf);
 942                         }
 943                         // highlight text
 944                         var selbeg, selend;
 945                         o = textarea;
 946                         if (tree.node[i].child.length == 0) {
 947                                 selbeg = o.value.indexOf(tree.node[i].name);
 948                                 selend = selbeg + tree.node[i].name.length;
 949                         } else {
 950                                 var left, leftd, str = o.value;
 951                                 left = tree.node[i]; leftd = 0;
 952                                 while (left.child.length) ++leftd, left = left.child[0]; // descend to the leftmost child
 953                                 selbeg = str.indexOf(left.name);
 954                                 for (--selbeg; selbeg >= 0; --selbeg) {
 955                                         if (str.charAt(selbeg) == '(') --leftd;
 956                                         if (leftd == 0) break;
 957                                 }
 958                                 var rght, rghtd;
 959                                 rght = tree.node[i]; rghtd = 0;
 960                                 while (rght.child.length) ++rghtd, rght = rght.child[rght.child.length-1];
 961                                 selend = str.indexOf(rght.name) + rght.name.length;
 962                                 for (; selend < str.length; ++selend) {
 963                                         if (str.charAt(selend) == ')') --rghtd;
 964                                         if (rghtd == 0) break;
 965                                 }
 966                                 ++selend;
 967                         }
 968                         //o.focus();
 969                         if (o.setSelectionRange) {
 970                                 var j, nn, h = o.clientHeight / o.rows;
 971                                 var str = o.value.substr(0, selbeg);
 972                                 for (j = nn = 0; j < selbeg && j < str.length; ++j)
 973                                         if (str.charAt(j) == '\n') ++nn;
 974                                 o.scrollTop = nn * h;
 975                                 o.setSelectionRange(selbeg, selend);
 976                         } else { // for IE
 977                                 var j, nn, r = o.createTextRange();
 978                                 var str = o.value.substr(0, selend);
 979                                 for (j = nn = 0; j < selbeg; ++j)
 980                                         if (str.charAt(j) == '\n') ++nn;
 981                                 selbeg -= nn;
 982                                 for (;j < selend; ++j)
 983                                         if (str.charAt(j) == '\n') ++nn;
 984                                 selend -= nn;
 985                                 r.collapse(true);
 986                                 r.moveEnd('character', selend);
 987                                 r.moveStart('character', selbeg);
 988                                 r.select();
 989                         }
 990                 }
 991         }
 992 }
 993
 994
 995 knhx_init = function(canvasId, textareaId) {
 996
 997         var kn_actions_html = '<h4>Actions</h4>'
 998                 + '<a href="javascript:void(0);" onClick="kn_actions.swap();">Swap</a>'
 999                 + '<a href="javascript:void(0);" onClick="kn_actions.sort();">Ladderize</a>'
1000                 + '<a href="javascript:void(0);" onClick="kn_actions.collapse();">Collapse</a>'
1001                 + '<a href="javascript:void(0);" onClick="kn_actions.reroot();">Reroot</a>'
1002                 + '<a href="javascript:void(0);" onClick="kn_actions.move();">Move</a>'
1003                 + '<a href="javascript:void(0);" onClick="kn_actions.multifurcate();">Multifurcate</a>'
1004                 + '<a href="javascript:void(0);" onClick="kn_actions.remove();">Remove</a>'
1005                 + '<a href="javascript:void(0);" onClick="kn_actions.highlight(\'none\');" class="alt">&nbsp;</a>'
1006                 + '<a href="javascript:void(0);" class="alt" onClick="kn_actions.highlight(\'red\');" style="background-color:#FFD8D0;">&nbsp;</a>'
1007                 + '<a href="javascript:void(0);" class="alt" onClick="kn_actions.highlight(\'green\');" style="background-color:#D0FFC0;">&nbsp;</a>'
1008                 + '<a href="javascript:void(0);" onClick="kn_actions.highlight(\'blue\');" class="alt" style="background-color:#C0D8FF;">&nbsp;</a>'
1009                 + '<a href="javascript:void(0);" onClick="kn_actions.highlight(\'yellow\');" class="alt" style="background-color:#FFFFC8;">&nbsp;</a>'
1010                 + '<a href="javascript:void(0);" onClick="kn_actions.highlight(\'cyan\');" class="alt" style="background-color:#D8FFFF;">&nbsp;</a>'
1011
1012         var menu_html = function() {
1013                 return '<h4>Menu</h4>'
1014                 + '<a href="javascript:void(0);" onClick="kn_actions.plot_str();">Draw tree</a>'
1015                 + '<a href="javascript:void(0);" onClick="window.open(document.getElementById(\''+canvasId+'\').toDataURL(\'image/png\'));">Export to PNG</a>'
1016                 + '<a href="javascript:void(0);" onClick="kn_actions.undo_redo();">Undo/Redo</a>'
1017                 + '<a href="javascript:void(0);" style="display: inline" onClick="kn_search_leaf(kn_g_tree,document.getElementById(\'searchLeaf\').value);kn_actions.plot();">Search</a>: <input id="searchLeaf" size=12>'
1018                 + '<h4>Configurations</h4>'
1019                 + '<table><tr><td>Width:<td><input size=5 value="' + kn_g_conf.width + '" onBlur="kn_g_conf.width=this.value;">'
1020                 + '<tr><td>Font size:<td><input size=5 value="' + kn_g_conf.fontsize + '" onBlur="kn_g_conf.fontsize=this.value;">'
1021                 + '<tr><td>Spacing:<td><input size=5 value="' + kn_g_conf.yskip + '" onBlur="kn_g_conf.yskip=this.value;">'
1022                 + '<tr><td>2nd label:<td><input size=10 value="' + kn_g_conf.regex + '" onBlur="kn_g_conf.regex=this.value;">'
1023             + '<tr><td>Phylogram:<td><input type="checkbox" '+(kn_g_conf.is_real? 'checked="yes"':'')+'" onChange="kn_g_conf.is_real=this.checked;">'
1024             + '<tr><td>Circular:<td><input type="checkbox" '+(kn_g_conf.is_circular? 'checked="yes"':'')+'" onChange="kn_g_conf.is_circular=this.checked;">'
1025                 + '</table>'
1026                 + '<h4>Information</h4>'
1027                 + '<table><tr><td># leaves:<td>'+(kn_g_tree?kn_g_tree.n_tips:0)
1028                 + '<tr><td># nodes:<td>'+(kn_g_tree?kn_g_tree.node.length:0)
1029                 + '<tr><td>Run time:<td>'+kn_g_conf.runtime+' sec'
1030                 + '</table>'
1031         }
1032
1033         function ev_canvas(ev) {
1034                 if (ev.layerX || ev.layerX == 0) { // Firefox
1035                         ev._x = ev.layerX;
1036                         ev._y = ev.layerY;
1037                 } else if (ev.offsetX || ev.offsetX == 0) { // Opera
1038                         ev._x = ev.offsetX;
1039                         ev._y = ev.offsetY;
1040                 }
1041                 if (navigator.appName == "Microsoft Internet Explorer") { // for IE8
1042                         /* When we click a node on the IE8 canvas, ev.offsetX gives
1043                          * the offset inside the node instead of inside the canvas.
1044                          * We have to do something nasty here... */
1045                         var d = document.body;
1046                         var o = document.getElementById("canvasContainer");
1047                         ev._x = ev.clientX - (o.offsetLeft - d.scrollLeft) - 3;
1048                         ev._y = ev.clientY - (o.offsetTop - d.scrollTop) - 3;
1049                 }
1050                 if (kn_g_tree) {
1051                         var id = kn_actions.get(ev._x, ev._y);
1052                         if (id >= 0) {
1053                                 kn_actions.set_id(id);
1054                                 if (kn_g_tree.active_node == null) popmenu.show(ev, kn_actions_html, "98px");
1055                                 else kn_actions.move();
1056                         } else popmenu.show(ev, menu_html());
1057                 } else popmenu.show(ev, menu_html());
1058         }
1059
1060         var canvas = document.getElementById(canvasId);
1061         var textarea = document.getElementById(textareaId);
1062
1063         kn_actions.init(canvas, textarea);
1064         if (canvas.addEventListener) canvas.addEventListener('click', ev_canvas, false);
1065         else canvas.attachEvent('onclick', ev_canvas);
1066
1067         var insert_elements = function() {
1068                 // put the canvas in a container
1069                 var o = document.createElement("div");
1070                 o.setAttribute('id', 'canvasContainer');
1071                 o.setAttribute('style', 'position: relative;');
1072                 var canvas_parent = canvas.parentNode || canvas.parent;
1073                 canvas_parent.removeChild(canvas);
1074                 canvas_parent.appendChild(o);
1075                 o.appendChild(canvas);
1076         }
1077
1078         insert_elements();
1079 }
1080
1081 /********************************
1082  * Cross-domain request via YQL *
1083  ********************************/
1084
1085 function xss_query_core(jsurl) {
1086         var script_id, script = document.createElement('script');
1087         script.setAttribute('type', 'text/javascript');
1088         script.setAttribute('src', jsurl);
1089         script.setAttribute('id', 'script_id');
1090         script_id = document.getElementById('script_id');
1091         if (script_id) document.getElementsByTagName('head')[0].removeChild(script_id);
1092         document.getElementsByTagName('head')[0].appendChild(script);
1093 //      document.getElementById('nhx').value = jsurl;
1094 }
1095
1096 function xss_query(url) {
1097         document.getElementById('nhx').value = "Please wait while the tree being retrieved...\n";
1098         xss_query_core("http://query.yahooapis.com/v1/public/yql?callback=xss_callback&q="
1099                                    + encodeURIComponent('select * from html where url="' + url + '"'));
1100 }
1101
1102 function xss_callback(data) {
1103         var str = data.results[0];
1104         var beg = str.indexOf('('), end = str.lastIndexOf(')');
1105         document.getElementById('nhx').value = str.substr(beg, end - beg + 1).replace(/&amp;/ig, "&")
1106                 .replace(/\n +/g, "\n").replace(/&quot;/, '"').replace(/&lt;/g, "<").replace(/&gt;/g, ">");
1107 }