src/data/Tree.js

   1 /*!
   2  * Ext JS Library 3.3.1
   3  * Copyright(c) 2006-2010 Sencha Inc.
   4  * licensing@sencha.com
   5  * http://www.sencha.com/license
   6  */
   7 /**
   8  * @class Ext.data.Tree
   9  * @extends Ext.util.Observable
  10  * Represents a tree data structure and bubbles all the events for its nodes. The nodes
  11  * in the tree have most standard DOM functionality.
  12  * @constructor
  13  * @param {Node} root (optional) The root node
  14  */
  15 Ext.data.Tree = Ext.extend(Ext.util.Observable, {
  16
  17     constructor: function(root){
  18         this.nodeHash = {};
  19         /**
  20          * The root node for this tree
  21          * @type Node
  22          */
  23         this.root = null;
  24         if(root){
  25             this.setRootNode(root);
  26         }
  27         this.addEvents(
  28             /**
  29              * @event append
  30              * Fires when a new child node is appended to a node in this tree.
  31              * @param {Tree} tree The owner tree
  32              * @param {Node} parent The parent node
  33              * @param {Node} node The newly appended node
  34              * @param {Number} index The index of the newly appended node
  35              */
  36             "append",
  37             /**
  38              * @event remove
  39              * Fires when a child node is removed from a node in this tree.
  40              * @param {Tree} tree The owner tree
  41              * @param {Node} parent The parent node
  42              * @param {Node} node The child node removed
  43              */
  44             "remove",
  45             /**
  46              * @event move
  47              * Fires when a node is moved to a new location in the tree
  48              * @param {Tree} tree The owner tree
  49              * @param {Node} node The node moved
  50              * @param {Node} oldParent The old parent of this node
  51              * @param {Node} newParent The new parent of this node
  52              * @param {Number} index The index it was moved to
  53              */
  54             "move",
  55             /**
  56              * @event insert
  57              * Fires when a new child node is inserted in a node in this tree.
  58              * @param {Tree} tree The owner tree
  59              * @param {Node} parent The parent node
  60              * @param {Node} node The child node inserted
  61              * @param {Node} refNode The child node the node was inserted before
  62              */
  63             "insert",
  64             /**
  65              * @event beforeappend
  66              * Fires before a new child is appended to a node in this tree, return false to cancel the append.
  67              * @param {Tree} tree The owner tree
  68              * @param {Node} parent The parent node
  69              * @param {Node} node The child node to be appended
  70              */
  71             "beforeappend",
  72             /**
  73              * @event beforeremove
  74              * Fires before a child is removed from a node in this tree, return false to cancel the remove.
  75              * @param {Tree} tree The owner tree
  76              * @param {Node} parent The parent node
  77              * @param {Node} node The child node to be removed
  78              */
  79             "beforeremove",
  80             /**
  81              * @event beforemove
  82              * Fires before a node is moved to a new location in the tree. Return false to cancel the move.
  83              * @param {Tree} tree The owner tree
  84              * @param {Node} node The node being moved
  85              * @param {Node} oldParent The parent of the node
  86              * @param {Node} newParent The new parent the node is moving to
  87              * @param {Number} index The index it is being moved to
  88              */
  89             "beforemove",
  90             /**
  91              * @event beforeinsert
  92              * Fires before a new child is inserted in a node in this tree, return false to cancel the insert.
  93              * @param {Tree} tree The owner tree
  94              * @param {Node} parent The parent node
  95              * @param {Node} node The child node to be inserted
  96              * @param {Node} refNode The child node the node is being inserted before
  97              */
  98             "beforeinsert"
  99         );
 100         Ext.data.Tree.superclass.constructor.call(this);
 101     },
 102
 103     /**
 104      * @cfg {String} pathSeparator
 105      * The token used to separate paths in node ids (defaults to '/').
 106      */
 107     pathSeparator: "/",
 108
 109     // private
 110     proxyNodeEvent : function(){
 111         return this.fireEvent.apply(this, arguments);
 112     },
 113
 114     /**
 115      * Returns the root node for this tree.
 116      * @return {Node}
 117      */
 118     getRootNode : function(){
 119         return this.root;
 120     },
 121
 122     /**
 123      * Sets the root node for this tree.
 124      * @param {Node} node
 125      * @return {Node}
 126      */
 127     setRootNode : function(node){
 128         this.root = node;
 129         node.ownerTree = this;
 130         node.isRoot = true;
 131         this.registerNode(node);
 132         return node;
 133     },
 134
 135     /**
 136      * Gets a node in this tree by its id.
 137      * @param {String} id
 138      * @return {Node}
 139      */
 140     getNodeById : function(id){
 141         return this.nodeHash[id];
 142     },
 143
 144     // private
 145     registerNode : function(node){
 146         this.nodeHash[node.id] = node;
 147     },
 148
 149     // private
 150     unregisterNode : function(node){
 151         delete this.nodeHash[node.id];
 152     },
 153
 154     toString : function(){
 155         return "[Tree"+(this.id?" "+this.id:"")+"]";
 156     }
 157 });
 158
 159 /**
 160  * @class Ext.data.Node
 161  * @extends Ext.util.Observable
 162  * @cfg {Boolean} leaf true if this node is a leaf and does not have children
 163  * @cfg {String} id The id for this node. If one is not specified, one is generated.
 164  * @constructor
 165  * @param {Object} attributes The attributes/config for the node
 166  */
 167 Ext.data.Node = Ext.extend(Ext.util.Observable, {
 168
 169     constructor: function(attributes){
 170         /**
 171          * The attributes supplied for the node. You can use this property to access any custom attributes you supplied.
 172          * @type {Object}
 173          */
 174         this.attributes = attributes || {};
 175         this.leaf = this.attributes.leaf;
 176         /**
 177          * The node id. @type String
 178          */
 179         this.id = this.attributes.id;
 180         if(!this.id){
 181             this.id = Ext.id(null, "xnode-");
 182             this.attributes.id = this.id;
 183         }
 184         /**
 185          * All child nodes of this node. @type Array
 186          */
 187         this.childNodes = [];
 188         /**
 189          * The parent node for this node. @type Node
 190          */
 191         this.parentNode = null;
 192         /**
 193          * The first direct child node of this node, or null if this node has no child nodes. @type Node
 194          */
 195         this.firstChild = null;
 196         /**
 197          * The last direct child node of this node, or null if this node has no child nodes. @type Node
 198          */
 199         this.lastChild = null;
 200         /**
 201          * The node immediately preceding this node in the tree, or null if there is no sibling node. @type Node
 202          */
 203         this.previousSibling = null;
 204         /**
 205          * The node immediately following this node in the tree, or null if there is no sibling node. @type Node
 206          */
 207         this.nextSibling = null;
 208
 209         this.addEvents({
 210             /**
 211              * @event append
 212              * Fires when a new child node is appended
 213              * @param {Tree} tree The owner tree
 214              * @param {Node} this This node
 215              * @param {Node} node The newly appended node
 216              * @param {Number} index The index of the newly appended node
 217              */
 218             "append" : true,
 219             /**
 220              * @event remove
 221              * Fires when a child node is removed
 222              * @param {Tree} tree The owner tree
 223              * @param {Node} this This node
 224              * @param {Node} node The removed node
 225              */
 226             "remove" : true,
 227             /**
 228              * @event move
 229              * Fires when this node is moved to a new location in the tree
 230              * @param {Tree} tree The owner tree
 231              * @param {Node} this This node
 232              * @param {Node} oldParent The old parent of this node
 233              * @param {Node} newParent The new parent of this node
 234              * @param {Number} index The index it was moved to
 235              */
 236             "move" : true,
 237             /**
 238              * @event insert
 239              * Fires when a new child node is inserted.
 240              * @param {Tree} tree The owner tree
 241              * @param {Node} this This node
 242              * @param {Node} node The child node inserted
 243              * @param {Node} refNode The child node the node was inserted before
 244              */
 245             "insert" : true,
 246             /**
 247              * @event beforeappend
 248              * Fires before a new child is appended, return false to cancel the append.
 249              * @param {Tree} tree The owner tree
 250              * @param {Node} this This node
 251              * @param {Node} node The child node to be appended
 252              */
 253             "beforeappend" : true,
 254             /**
 255              * @event beforeremove
 256              * Fires before a child is removed, return false to cancel the remove.
 257              * @param {Tree} tree The owner tree
 258              * @param {Node} this This node
 259              * @param {Node} node The child node to be removed
 260              */
 261             "beforeremove" : true,
 262             /**
 263              * @event beforemove
 264              * Fires before this node is moved to a new location in the tree. Return false to cancel the move.
 265              * @param {Tree} tree The owner tree
 266              * @param {Node} this This node
 267              * @param {Node} oldParent The parent of this node
 268              * @param {Node} newParent The new parent this node is moving to
 269              * @param {Number} index The index it is being moved to
 270              */
 271             "beforemove" : true,
 272              /**
 273               * @event beforeinsert
 274               * Fires before a new child is inserted, return false to cancel the insert.
 275               * @param {Tree} tree The owner tree
 276               * @param {Node} this This node
 277               * @param {Node} node The child node to be inserted
 278               * @param {Node} refNode The child node the node is being inserted before
 279               */
 280             "beforeinsert" : true
 281         });
 282         this.listeners = this.attributes.listeners;
 283         Ext.data.Node.superclass.constructor.call(this);
 284     },
 285
 286     // private
 287     fireEvent : function(evtName){
 288         // first do standard event for this node
 289         if(Ext.data.Node.superclass.fireEvent.apply(this, arguments) === false){
 290             return false;
 291         }
 292         // then bubble it up to the tree if the event wasn't cancelled
 293         var ot = this.getOwnerTree();
 294         if(ot){
 295             if(ot.proxyNodeEvent.apply(ot, arguments) === false){
 296                 return false;
 297             }
 298         }
 299         return true;
 300     },
 301
 302     /**
 303      * Returns true if this node is a leaf
 304      * @return {Boolean}
 305      */
 306     isLeaf : function(){
 307         return this.leaf === true;
 308     },
 309
 310     // private
 311     setFirstChild : function(node){
 312         this.firstChild = node;
 313     },
 314
 315     //private
 316     setLastChild : function(node){
 317         this.lastChild = node;
 318     },
 319
 320
 321     /**
 322      * Returns true if this node is the last child of its parent
 323      * @return {Boolean}
 324      */
 325     isLast : function(){
 326        return (!this.parentNode ? true : this.parentNode.lastChild == this);
 327     },
 328
 329     /**
 330      * Returns true if this node is the first child of its parent
 331      * @return {Boolean}
 332      */
 333     isFirst : function(){
 334        return (!this.parentNode ? true : this.parentNode.firstChild == this);
 335     },
 336
 337     /**
 338      * Returns true if this node has one or more child nodes, else false.
 339      * @return {Boolean}
 340      */
 341     hasChildNodes : function(){
 342         return !this.isLeaf() && this.childNodes.length > 0;
 343     },
 344
 345     /**
 346      * Returns true if this node has one or more child nodes, or if the <tt>expandable</tt>
 347      * node attribute is explicitly specified as true (see {@link #attributes}), otherwise returns false.
 348      * @return {Boolean}
 349      */
 350     isExpandable : function(){
 351         return this.attributes.expandable || this.hasChildNodes();
 352     },
 353
 354     /**
 355      * Insert node(s) as the last child node of this node.
 356      * @param {Node/Array} node The node or Array of nodes to append
 357      * @return {Node} The appended node if single append, or null if an array was passed
 358      */
 359     appendChild : function(node){
 360         var multi = false;
 361         if(Ext.isArray(node)){
 362             multi = node;
 363         }else if(arguments.length > 1){
 364             multi = arguments;
 365         }
 366         // if passed an array or multiple args do them one by one
 367         if(multi){
 368             for(var i = 0, len = multi.length; i < len; i++) {
 369                 this.appendChild(multi[i]);
 370             }
 371         }else{
 372             if(this.fireEvent("beforeappend", this.ownerTree, this, node) === false){
 373                 return false;
 374             }
 375             var index = this.childNodes.length;
 376             var oldParent = node.parentNode;
 377             // it's a move, make sure we move it cleanly
 378             if(oldParent){
 379                 if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index) === false){
 380                     return false;
 381                 }
 382                 oldParent.removeChild(node);
 383             }
 384             index = this.childNodes.length;
 385             if(index === 0){
 386                 this.setFirstChild(node);
 387             }
 388             this.childNodes.push(node);
 389             node.parentNode = this;
 390             var ps = this.childNodes[index-1];
 391             if(ps){
 392                 node.previousSibling = ps;
 393                 ps.nextSibling = node;
 394             }else{
 395                 node.previousSibling = null;
 396             }
 397             node.nextSibling = null;
 398             this.setLastChild(node);
 399             node.setOwnerTree(this.getOwnerTree());
 400             this.fireEvent("append", this.ownerTree, this, node, index);
 401             if(oldParent){
 402                 node.fireEvent("move", this.ownerTree, node, oldParent, this, index);
 403             }
 404             return node;
 405         }
 406     },
 407
 408     /**
 409      * Removes a child node from this node.
 410      * @param {Node} node The node to remove
 411      * @param {Boolean} destroy <tt>true</tt> to destroy the node upon removal. Defaults to <tt>false</tt>.
 412      * @return {Node} The removed node
 413      */
 414     removeChild : function(node, destroy){
 415         var index = this.childNodes.indexOf(node);
 416         if(index == -1){
 417             return false;
 418         }
 419         if(this.fireEvent("beforeremove", this.ownerTree, this, node) === false){
 420             return false;
 421         }
 422
 423         // remove it from childNodes collection
 424         this.childNodes.splice(index, 1);
 425
 426         // update siblings
 427         if(node.previousSibling){
 428             node.previousSibling.nextSibling = node.nextSibling;
 429         }
 430         if(node.nextSibling){
 431             node.nextSibling.previousSibling = node.previousSibling;
 432         }
 433
 434         // update child refs
 435         if(this.firstChild == node){
 436             this.setFirstChild(node.nextSibling);
 437         }
 438         if(this.lastChild == node){
 439             this.setLastChild(node.previousSibling);
 440         }
 441
 442         this.fireEvent("remove", this.ownerTree, this, node);
 443         if(destroy){
 444             node.destroy(true);
 445         }else{
 446             node.clear();
 447         }
 448         return node;
 449     },
 450
 451     // private
 452     clear : function(destroy){
 453         // clear any references from the node
 454         this.setOwnerTree(null, destroy);
 455         this.parentNode = this.previousSibling = this.nextSibling = null;
 456         if(destroy){
 457             this.firstChild = this.lastChild = null;
 458         }
 459     },
 460
 461     /**
 462      * Destroys the node.
 463      */
 464     destroy : function(/* private */ silent){
 465         /*
 466          * Silent is to be used in a number of cases
 467          * 1) When setRootNode is called.
 468          * 2) When destroy on the tree is called
 469          * 3) For destroying child nodes on a node
 470          */
 471         if(silent === true){
 472             this.purgeListeners();
 473             this.clear(true);
 474             Ext.each(this.childNodes, function(n){
 475                 n.destroy(true);
 476             });
 477             this.childNodes = null;
 478         }else{
 479             this.remove(true);
 480         }
 481     },
 482
 483     /**
 484      * Inserts the first node before the second node in this nodes childNodes collection.
 485      * @param {Node} node The node to insert
 486      * @param {Node} refNode The node to insert before (if null the node is appended)
 487      * @return {Node} The inserted node
 488      */
 489     insertBefore : function(node, refNode){
 490         if(!refNode){ // like standard Dom, refNode can be null for append
 491             return this.appendChild(node);
 492         }
 493         // nothing to do
 494         if(node == refNode){
 495             return false;
 496         }
 497
 498         if(this.fireEvent("beforeinsert", this.ownerTree, this, node, refNode) === false){
 499             return false;
 500         }
 501         var index = this.childNodes.indexOf(refNode);
 502         var oldParent = node.parentNode;
 503         var refIndex = index;
 504
 505         // when moving internally, indexes will change after remove
 506         if(oldParent == this && this.childNodes.indexOf(node) < index){
 507             refIndex--;
 508         }
 509
 510         // it's a move, make sure we move it cleanly
 511         if(oldParent){
 512             if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index, refNode) === false){
 513                 return false;
 514             }
 515             oldParent.removeChild(node);
 516         }
 517         if(refIndex === 0){
 518             this.setFirstChild(node);
 519         }
 520         this.childNodes.splice(refIndex, 0, node);
 521         node.parentNode = this;
 522         var ps = this.childNodes[refIndex-1];
 523         if(ps){
 524             node.previousSibling = ps;
 525             ps.nextSibling = node;
 526         }else{
 527             node.previousSibling = null;
 528         }
 529         node.nextSibling = refNode;
 530         refNode.previousSibling = node;
 531         node.setOwnerTree(this.getOwnerTree());
 532         this.fireEvent("insert", this.ownerTree, this, node, refNode);
 533         if(oldParent){
 534             node.fireEvent("move", this.ownerTree, node, oldParent, this, refIndex, refNode);
 535         }
 536         return node;
 537     },
 538
 539     /**
 540      * Removes this node from its parent
 541      * @param {Boolean} destroy <tt>true</tt> to destroy the node upon removal. Defaults to <tt>false</tt>.
 542      * @return {Node} this
 543      */
 544     remove : function(destroy){
 545         if (this.parentNode) {
 546             this.parentNode.removeChild(this, destroy);
 547         }
 548         return this;
 549     },
 550
 551     /**
 552      * Removes all child nodes from this node.
 553      * @param {Boolean} destroy <tt>true</tt> to destroy the node upon removal. Defaults to <tt>false</tt>.
 554      * @return {Node} this
 555      */
 556     removeAll : function(destroy){
 557         var cn = this.childNodes,
 558             n;
 559         while((n = cn[0])){
 560             this.removeChild(n, destroy);
 561         }
 562         return this;
 563     },
 564
 565     /**
 566      * Returns the child node at the specified index.
 567      * @param {Number} index
 568      * @return {Node}
 569      */
 570     item : function(index){
 571         return this.childNodes[index];
 572     },
 573
 574     /**
 575      * Replaces one child node in this node with another.
 576      * @param {Node} newChild The replacement node
 577      * @param {Node} oldChild The node to replace
 578      * @return {Node} The replaced node
 579      */
 580     replaceChild : function(newChild, oldChild){
 581         var s = oldChild ? oldChild.nextSibling : null;
 582         this.removeChild(oldChild);
 583         this.insertBefore(newChild, s);
 584         return oldChild;
 585     },
 586
 587     /**
 588      * Returns the index of a child node
 589      * @param {Node} node
 590      * @return {Number} The index of the node or -1 if it was not found
 591      */
 592     indexOf : function(child){
 593         return this.childNodes.indexOf(child);
 594     },
 595
 596     /**
 597      * Returns the tree this node is in.
 598      * @return {Tree}
 599      */
 600     getOwnerTree : function(){
 601         // if it doesn't have one, look for one
 602         if(!this.ownerTree){
 603             var p = this;
 604             while(p){
 605                 if(p.ownerTree){
 606                     this.ownerTree = p.ownerTree;
 607                     break;
 608                 }
 609                 p = p.parentNode;
 610             }
 611         }
 612         return this.ownerTree;
 613     },
 614
 615     /**
 616      * Returns depth of this node (the root node has a depth of 0)
 617      * @return {Number}
 618      */
 619     getDepth : function(){
 620         var depth = 0;
 621         var p = this;
 622         while(p.parentNode){
 623             ++depth;
 624             p = p.parentNode;
 625         }
 626         return depth;
 627     },
 628
 629     // private
 630     setOwnerTree : function(tree, destroy){
 631         // if it is a move, we need to update everyone
 632         if(tree != this.ownerTree){
 633             if(this.ownerTree){
 634                 this.ownerTree.unregisterNode(this);
 635             }
 636             this.ownerTree = tree;
 637             // If we're destroying, we don't need to recurse since it will be called on each child node
 638             if(destroy !== true){
 639                 Ext.each(this.childNodes, function(n){
 640                     n.setOwnerTree(tree);
 641                 });
 642             }
 643             if(tree){
 644                 tree.registerNode(this);
 645             }
 646         }
 647     },
 648
 649     /**
 650      * Changes the id of this node.
 651      * @param {String} id The new id for the node.
 652      */
 653     setId: function(id){
 654         if(id !== this.id){
 655             var t = this.ownerTree;
 656             if(t){
 657                 t.unregisterNode(this);
 658             }
 659             this.id = this.attributes.id = id;
 660             if(t){
 661                 t.registerNode(this);
 662             }
 663             this.onIdChange(id);
 664         }
 665     },
 666
 667     // private
 668     onIdChange: Ext.emptyFn,
 669
 670     /**
 671      * Returns the path for this node. The path can be used to expand or select this node programmatically.
 672      * @param {String} attr (optional) The attr to use for the path (defaults to the node's id)
 673      * @return {String} The path
 674      */
 675     getPath : function(attr){
 676         attr = attr || "id";
 677         var p = this.parentNode;
 678         var b = [this.attributes[attr]];
 679         while(p){
 680             b.unshift(p.attributes[attr]);
 681             p = p.parentNode;
 682         }
 683         var sep = this.getOwnerTree().pathSeparator;
 684         return sep + b.join(sep);
 685     },
 686
 687     /**
 688      * Bubbles up the tree from this node, calling the specified function with each node. The arguments to the function
 689      * will be the args provided or the current node. If the function returns false at any point,
 690      * the bubble is stopped.
 691      * @param {Function} fn The function to call
 692      * @param {Object} scope (optional) The scope (<code>this</code> reference) in which the function is executed. Defaults to the current Node.
 693      * @param {Array} args (optional) The args to call the function with (default to passing the current Node)
 694      */
 695     bubble : function(fn, scope, args){
 696         var p = this;
 697         while(p){
 698             if(fn.apply(scope || p, args || [p]) === false){
 699                 break;
 700             }
 701             p = p.parentNode;
 702         }
 703     },
 704
 705     /**
 706      * Cascades down the tree from this node, calling the specified function with each node. The arguments to the function
 707      * will be the args provided or the current node. If the function returns false at any point,
 708      * the cascade is stopped on that branch.
 709      * @param {Function} fn The function to call
 710      * @param {Object} scope (optional) The scope (<code>this</code> reference) in which the function is executed. Defaults to the current Node.
 711      * @param {Array} args (optional) The args to call the function with (default to passing the current Node)
 712      */
 713     cascade : function(fn, scope, args){
 714         if(fn.apply(scope || this, args || [this]) !== false){
 715             var cs = this.childNodes;
 716             for(var i = 0, len = cs.length; i < len; i++) {
 717                 cs[i].cascade(fn, scope, args);
 718             }
 719         }
 720     },
 721
 722     /**
 723      * Interates the child nodes of this node, calling the specified function with each node. The arguments to the function
 724      * will be the args provided or the current node. If the function returns false at any point,
 725      * the iteration stops.
 726      * @param {Function} fn The function to call
 727      * @param {Object} scope (optional) The scope (<code>this</code> reference) in which the function is executed. Defaults to the current Node in the iteration.
 728      * @param {Array} args (optional) The args to call the function with (default to passing the current Node)
 729      */
 730     eachChild : function(fn, scope, args){
 731         var cs = this.childNodes;
 732         for(var i = 0, len = cs.length; i < len; i++) {
 733             if(fn.apply(scope || cs[i], args || [cs[i]]) === false){
 734                 break;
 735             }
 736         }
 737     },
 738
 739     /**
 740      * Finds the first child that has the attribute with the specified value.
 741      * @param {String} attribute The attribute name
 742      * @param {Mixed} value The value to search for
 743      * @param {Boolean} deep (Optional) True to search through nodes deeper than the immediate children
 744      * @return {Node} The found child or null if none was found
 745      */
 746     findChild : function(attribute, value, deep){
 747         return this.findChildBy(function(){
 748             return this.attributes[attribute] == value;
 749         }, null, deep);
 750     },
 751
 752     /**
 753      * Finds the first child by a custom function. The child matches if the function passed returns <code>true</code>.
 754      * @param {Function} fn A function which must return <code>true</code> if the passed Node is the required Node.
 755      * @param {Object} scope (optional) The scope (<code>this</code> reference) in which the function is executed. Defaults to the Node being tested.
 756      * @param {Boolean} deep (Optional) True to search through nodes deeper than the immediate children
 757      * @return {Node} The found child or null if none was found
 758      */
 759     findChildBy : function(fn, scope, deep){
 760         var cs = this.childNodes,
 761             len = cs.length,
 762             i = 0,
 763             n,
 764             res;
 765         for(; i < len; i++){
 766             n = cs[i];
 767             if(fn.call(scope || n, n) === true){
 768                 return n;
 769             }else if (deep){
 770                 res = n.findChildBy(fn, scope, deep);
 771                 if(res != null){
 772                     return res;
 773                 }
 774             }
 775
 776         }
 777         return null;
 778     },
 779
 780     /**
 781      * Sorts this nodes children using the supplied sort function.
 782      * @param {Function} fn A function which, when passed two Nodes, returns -1, 0 or 1 depending upon required sort order.
 783      * @param {Object} scope (optional)The scope (<code>this</code> reference) in which the function is executed. Defaults to the browser window.
 784      */
 785     sort : function(fn, scope){
 786         var cs = this.childNodes;
 787         var len = cs.length;
 788         if(len > 0){
 789             var sortFn = scope ? function(){fn.apply(scope, arguments);} : fn;
 790             cs.sort(sortFn);
 791             for(var i = 0; i < len; i++){
 792                 var n = cs[i];
 793                 n.previousSibling = cs[i-1];
 794                 n.nextSibling = cs[i+1];
 795                 if(i === 0){
 796                     this.setFirstChild(n);
 797                 }
 798                 if(i == len-1){
 799                     this.setLastChild(n);
 800                 }
 801             }
 802         }
 803     },
 804
 805     /**
 806      * Returns true if this node is an ancestor (at any point) of the passed node.
 807      * @param {Node} node
 808      * @return {Boolean}
 809      */
 810     contains : function(node){
 811         return node.isAncestor(this);
 812     },
 813
 814     /**
 815      * Returns true if the passed node is an ancestor (at any point) of this node.
 816      * @param {Node} node
 817      * @return {Boolean}
 818      */
 819     isAncestor : function(node){
 820         var p = this.parentNode;
 821         while(p){
 822             if(p == node){
 823                 return true;
 824             }
 825             p = p.parentNode;
 826         }
 827         return false;
 828     },
 829
 830     toString : function(){
 831         return "[Node"+(this.id?" "+this.id:"")+"]";
 832     }
 833 });