git.roojs.org Git - roojs1/blob - Roo/data/Tree.js

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