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
 183     /**
 184      * All child nodes of this node. @type Array
 185      */
 186     this.childNodes = [];
 187     if(!this.childNodes.indexOf){ // indexOf is a must
 188         this.childNodes.indexOf = function(o){
 189             for(var i = 0, len = this.length; i < len; i++){
 190                 if(this[i] == o) {
 191                     return i;
 192                 }
 193             }
 194             return -1;
 195         };
 196     }
 197     /**
 198      * The parent node for this node. @type Node
 199      */
 200     this.parentNode = null;
 201     /**
 202      * The first direct child node of this node, or null if this node has no child nodes. @type Node
 203      */
 204     this.firstChild = null;
 205     /**
 206      * The last direct child node of this node, or null if this node has no child nodes. @type Node
 207      */
 208     this.lastChild = null;
 209     /**
 210      * The node immediately preceding this node in the tree, or null if there is no sibling node. @type Node
 211      */
 212     this.previousSibling = null;
 213     /**
 214      * The node immediately following this node in the tree, or null if there is no sibling node. @type Node
 215      */
 216     this.nextSibling = null;
 217
 218     this.addEvents({
 219        /**
 220         * @event append
 221         * Fires when a new child node is appended
 222         * @param {Tree} tree The owner tree
 223         * @param {Node} this This node
 224         * @param {Node} node The newly appended node
 225         * @param {Number} index The index of the newly appended node
 226         */
 227        "append" : true,
 228        /**
 229         * @event remove
 230         * Fires when a child node is removed
 231         * @param {Tree} tree The owner tree
 232         * @param {Node} this This node
 233         * @param {Node} node The removed node
 234         */
 235        "remove" : true,
 236        /**
 237         * @event move
 238         * Fires when this node is moved to a new location in the tree
 239         * @param {Tree} tree The owner tree
 240         * @param {Node} this This node
 241         * @param {Node} oldParent The old parent of this node
 242         * @param {Node} newParent The new parent of this node
 243         * @param {Number} index The index it was moved to
 244         */
 245        "move" : true,
 246        /**
 247         * @event insert
 248         * Fires when a new child node is inserted.
 249         * @param {Tree} tree The owner tree
 250         * @param {Node} this This node
 251         * @param {Node} node The child node inserted
 252         * @param {Node} refNode The child node the node was inserted before
 253         */
 254        "insert" : true,
 255        /**
 256         * @event beforeappend
 257         * Fires before a new child is appended, return false to cancel the append.
 258         * @param {Tree} tree The owner tree
 259         * @param {Node} this This node
 260         * @param {Node} node The child node to be appended
 261         */
 262        "beforeappend" : true,
 263        /**
 264         * @event beforeremove
 265         * Fires before a child is removed, return false to cancel the remove.
 266         * @param {Tree} tree The owner tree
 267         * @param {Node} this This node
 268         * @param {Node} node The child node to be removed
 269         */
 270        "beforeremove" : true,
 271        /**
 272         * @event beforemove
 273         * Fires before this node is moved to a new location in the tree. Return false to cancel the move.
 274         * @param {Tree} tree The owner tree
 275         * @param {Node} this This node
 276         * @param {Node} oldParent The parent of this node
 277         * @param {Node} newParent The new parent this node is moving to
 278         * @param {Number} index The index it is being moved to
 279         */
 280        "beforemove" : true,
 281        /**
 282         * @event beforeinsert
 283         * Fires before a new child is inserted, return false to cancel the insert.
 284         * @param {Tree} tree The owner tree
 285         * @param {Node} this This node
 286         * @param {Node} node The child node to be inserted
 287         * @param {Node} refNode The child node the node is being inserted before
 288         */
 289        "beforeinsert" : true
 290    });
 291     this.listeners = this.attributes.listeners;
 292     Roo.data.Node.superclass.constructor.call(this);
 293 };
 294
 295 Roo.extend(Roo.data.Node, Roo.util.Observable, {
 296     fireEvent : function(evtName){
 297         // first do standard event for this node
 298         if(Roo.data.Node.superclass.fireEvent.apply(this, arguments) === false){
 299             return false;
 300         }
 301         // then bubble it up to the tree if the event wasn't cancelled
 302         var ot = this.getOwnerTree();
 303         if(ot){
 304             if(ot.proxyNodeEvent.apply(ot, arguments) === false){
 305                 return false;
 306             }
 307         }
 308         return true;
 309     },
 310
 311     /**
 312      * Returns true if this node is a leaf
 313      * @return {Boolean}
 314      */
 315     isLeaf : function(){
 316         return this.leaf === true;
 317     },
 318
 319     // private
 320     setFirstChild : function(node){
 321         this.firstChild = node;
 322     },
 323
 324     //private
 325     setLastChild : function(node){
 326         this.lastChild = node;
 327     },
 328
 329
 330     /**
 331      * Returns true if this node is the last child of its parent
 332      * @return {Boolean}
 333      */
 334     isLast : function(){
 335        return (!this.parentNode ? true : this.parentNode.lastChild == this);
 336     },
 337
 338     /**
 339      * Returns true if this node is the first child of its parent
 340      * @return {Boolean}
 341      */
 342     isFirst : function(){
 343        return (!this.parentNode ? true : this.parentNode.firstChild == this);
 344     },
 345
 346     hasChildNodes : function(){
 347         return !this.isLeaf() && this.childNodes.length > 0;
 348     },
 349
 350     /**
 351      * Insert node(s) as the last child node of this node.
 352      * @param {Node/Array} node The node or Array of nodes to append
 353      * @return {Node} The appended node if single append, or null if an array was passed
 354      */
 355     appendChild : function(node){
 356         var multi = false;
 357         if(node instanceof Array){
 358             multi = node;
 359         }else if(arguments.length > 1){
 360             multi = arguments;
 361         }
 362
 363         // if passed an array or multiple args do them one by one
 364         if(multi){
 365             for(var i = 0, len = multi.length; i < len; i++) {
 366                 this.appendChild(multi[i]);
 367             }
 368         }else{
 369             if(this.fireEvent("beforeappend", this.ownerTree, this, node) === false){
 370                 return false;
 371             }
 372             var index = this.childNodes.length;
 373             var oldParent = node.parentNode;
 374             // it's a move, make sure we move it cleanly
 375             if(oldParent){
 376                 if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index) === false){
 377                     return false;
 378                 }
 379                 oldParent.removeChild(node);
 380             }
 381
 382             index = this.childNodes.length;
 383             if(index == 0){
 384                 this.setFirstChild(node);
 385             }
 386             this.childNodes.push(node);
 387             node.parentNode = this;
 388             var ps = this.childNodes[index-1];
 389             if(ps){
 390                 node.previousSibling = ps;
 391                 ps.nextSibling = node;
 392             }else{
 393                 node.previousSibling = null;
 394             }
 395             node.nextSibling = null;
 396             this.setLastChild(node);
 397             node.setOwnerTree(this.getOwnerTree());
 398             this.fireEvent("append", this.ownerTree, this, node, index);
 399             if(this.ownerTree) {
 400                 this.ownerTree.fireEvent("appendnode", this, node, index);
 401             }
 402             if(oldParent){
 403                 node.fireEvent("move", this.ownerTree, node, oldParent, this, index);
 404             }
 405             return node;
 406         }
 407     },
 408
 409     /**
 410      * Removes a child node from this node.
 411      * @param {Node} node The node to remove
 412      * @return {Node} The removed node
 413      */
 414     removeChild : function(node){
 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         node.setOwnerTree(null);
 443         // clear any references from the node
 444         node.parentNode = null;
 445         node.previousSibling = null;
 446         node.nextSibling = null;
 447         this.fireEvent("remove", this.ownerTree, this, node);
 448         return node;
 449     },
 450
 451     /**
 452      * Inserts the first node before the second node in this nodes childNodes collection.
 453      * @param {Node} node The node to insert
 454      * @param {Node} refNode The node to insert before (if null the node is appended)
 455      * @return {Node} The inserted node
 456      */
 457     insertBefore : function(node, refNode){
 458         if(!refNode){ // like standard Dom, refNode can be null for append
 459             return this.appendChild(node);
 460         }
 461         // nothing to do
 462         if(node == refNode){
 463             return false;
 464         }
 465
 466         if(this.fireEvent("beforeinsert", this.ownerTree, this, node, refNode) === false){
 467             return false;
 468         }
 469         var index = this.childNodes.indexOf(refNode);
 470         var oldParent = node.parentNode;
 471         var refIndex = index;
 472
 473         // when moving internally, indexes will change after remove
 474         if(oldParent == this && this.childNodes.indexOf(node) < index){
 475             refIndex--;
 476         }
 477
 478         // it's a move, make sure we move it cleanly
 479         if(oldParent){
 480             if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index, refNode) === false){
 481                 return false;
 482             }
 483             oldParent.removeChild(node);
 484         }
 485         if(refIndex == 0){
 486             this.setFirstChild(node);
 487         }
 488         this.childNodes.splice(refIndex, 0, node);
 489         node.parentNode = this;
 490         var ps = this.childNodes[refIndex-1];
 491         if(ps){
 492             node.previousSibling = ps;
 493             ps.nextSibling = node;
 494         }else{
 495             node.previousSibling = null;
 496         }
 497         node.nextSibling = refNode;
 498         refNode.previousSibling = node;
 499         node.setOwnerTree(this.getOwnerTree());
 500         this.fireEvent("insert", this.ownerTree, this, node, refNode);
 501         if(oldParent){
 502             node.fireEvent("move", this.ownerTree, node, oldParent, this, refIndex, refNode);
 503         }
 504         return node;
 505     },
 506
 507     /**
 508      * Returns the child node at the specified index.
 509      * @param {Number} index
 510      * @return {Node}
 511      */
 512     item : function(index){
 513         return this.childNodes[index];
 514     },
 515
 516     /**
 517      * Replaces one child node in this node with another.
 518      * @param {Node} newChild The replacement node
 519      * @param {Node} oldChild The node to replace
 520      * @return {Node} The replaced node
 521      */
 522     replaceChild : function(newChild, oldChild){
 523         this.insertBefore(newChild, oldChild);
 524         this.removeChild(oldChild);
 525         return oldChild;
 526     },
 527
 528     /**
 529      * Returns the index of a child node
 530      * @param {Node} node
 531      * @return {Number} The index of the node or -1 if it was not found
 532      */
 533     indexOf : function(child){
 534         return this.childNodes.indexOf(child);
 535     },
 536
 537     /**
 538      * Returns the tree this node is in.
 539      * @return {Tree}
 540      */
 541     getOwnerTree : function(){
 542         // if it doesn't have one, look for one
 543         if(!this.ownerTree){
 544             var p = this;
 545             while(p){
 546                 if(p.ownerTree){
 547                     this.ownerTree = p.ownerTree;
 548                     break;
 549                 }
 550                 p = p.parentNode;
 551             }
 552         }
 553         return this.ownerTree;
 554     },
 555
 556     /**
 557      * Returns depth of this node (the root node has a depth of 0)
 558      * @return {Number}
 559      */
 560     getDepth : function(){
 561         var depth = 0;
 562         var p = this;
 563         while(p.parentNode){
 564             ++depth;
 565             p = p.parentNode;
 566         }
 567         return depth;
 568     },
 569
 570     // private
 571     setOwnerTree : function(tree){
 572         // if it's move, we need to update everyone
 573         if(tree != this.ownerTree){
 574             if(this.ownerTree){
 575                 this.ownerTree.unregisterNode(this);
 576             }
 577             this.ownerTree = tree;
 578             var cs = this.childNodes;
 579             for(var i = 0, len = cs.length; i < len; i++) {
 580                 cs[i].setOwnerTree(tree);
 581             }
 582             if(tree){
 583                 tree.registerNode(this);
 584             }
 585         }
 586     },
 587
 588     /**
 589      * Returns the path for this node. The path can be used to expand or select this node programmatically.
 590      * @param {String} attr (optional) The attr to use for the path (defaults to the node's id)
 591      * @return {String} The path
 592      */
 593     getPath : function(attr){
 594         attr = attr || "id";
 595         var p = this.parentNode;
 596         var b = [this.attributes[attr]];
 597         while(p){
 598             b.unshift(p.attributes[attr]);
 599             p = p.parentNode;
 600         }
 601         var sep = this.getOwnerTree().pathSeparator;
 602         return sep + b.join(sep);
 603     },
 604
 605     /**
 606      * Bubbles up the tree from this node, calling the specified function with each node. The scope (<i>this</i>) of
 607      * function call will be the scope provided or the current node. The arguments to the function
 608      * will be the args provided or the current node. If the function returns false at any point,
 609      * the bubble is stopped.
 610      * @param {Function} fn The function to call
 611      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 612      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 613      */
 614     bubble : function(fn, scope, args){
 615         var p = this;
 616         while(p){
 617             if(fn.call(scope || p, args || p) === false){
 618                 break;
 619             }
 620             p = p.parentNode;
 621         }
 622     },
 623
 624     /**
 625      * Cascades down the tree from this node, calling the specified function with each node. The scope (<i>this</i>) of
 626      * function call will be the scope provided or the current node. The arguments to the function
 627      * will be the args provided or the current node. If the function returns false at any point,
 628      * the cascade is stopped on that branch.
 629      * @param {Function} fn The function to call
 630      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 631      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 632      */
 633     cascade : function(fn, scope, args){
 634         if(fn.call(scope || this, args || this) !== false){
 635             var cs = this.childNodes;
 636             for(var i = 0, len = cs.length; i < len; i++) {
 637                 cs[i].cascade(fn, scope, args);
 638             }
 639         }
 640     },
 641
 642     /**
 643      * Interates the child nodes of this node, calling the specified function with each node. The scope (<i>this</i>) of
 644      * function call will be the scope provided or the current node. The arguments to the function
 645      * will be the args provided or the current node. If the function returns false at any point,
 646      * the iteration stops.
 647      * @param {Function} fn The function to call
 648      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 649      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 650      */
 651     eachChild : function(fn, scope, args){
 652         var cs = this.childNodes;
 653         for(var i = 0, len = cs.length; i < len; i++) {
 654                 if(fn.call(scope || this, args || cs[i]) === false){
 655                     break;
 656                 }
 657         }
 658     },
 659
 660     /**
 661      * Finds the first child that has the attribute with the specified value.
 662      * @param {String} attribute The attribute name
 663      * @param {Mixed} value The value to search for
 664      * @return {Node} The found child or null if none was found
 665      */
 666     findChild : function(attribute, value){
 667         var cs = this.childNodes;
 668         for(var i = 0, len = cs.length; i < len; i++) {
 669                 if(cs[i].attributes[attribute] == value){
 670                     return cs[i];
 671                 }
 672         }
 673         return null;
 674     },
 675
 676     /**
 677      * Finds the first child by a custom function. The child matches if the function passed
 678      * returns true.
 679      * @param {Function} fn
 680      * @param {Object} scope (optional)
 681      * @return {Node} The found child or null if none was found
 682      */
 683     findChildBy : function(fn, scope){
 684         var cs = this.childNodes;
 685         for(var i = 0, len = cs.length; i < len; i++) {
 686                 if(fn.call(scope||cs[i], cs[i]) === true){
 687                     return cs[i];
 688                 }
 689         }
 690         return null;
 691     },
 692
 693     /**
 694      * Sorts this nodes children using the supplied sort function
 695      * @param {Function} fn
 696      * @param {Object} scope (optional)
 697      */
 698     sort : function(fn, scope){
 699         var cs = this.childNodes;
 700         var len = cs.length;
 701         if(len > 0){
 702             var sortFn = scope ? function(){fn.apply(scope, arguments);} : fn;
 703             cs.sort(sortFn);
 704             for(var i = 0; i < len; i++){
 705                 var n = cs[i];
 706                 n.previousSibling = cs[i-1];
 707                 n.nextSibling = cs[i+1];
 708                 if(i == 0){
 709                     this.setFirstChild(n);
 710                 }
 711                 if(i == len-1){
 712                     this.setLastChild(n);
 713                 }
 714             }
 715         }
 716     },
 717
 718     /**
 719      * Returns true if this node is an ancestor (at any point) of the passed node.
 720      * @param {Node} node
 721      * @return {Boolean}
 722      */
 723     contains : function(node){
 724         return node.isAncestor(this);
 725     },
 726
 727     /**
 728      * Returns true if the passed node is an ancestor (at any point) of this node.
 729      * @param {Node} node
 730      * @return {Boolean}
 731      */
 732     isAncestor : function(node){
 733         var p = this.parentNode;
 734         while(p){
 735             if(p == node){
 736                 return true;
 737             }
 738             p = p.parentNode;
 739         }
 740         return false;
 741     },
 742
 743     toString : function(){
 744         return "[Node"+(this.id?" "+this.id:"")+"]";
 745     }
 746 });