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