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         // if passed an array or multiple args do them one by one
 363         if(multi){
 364             for(var i = 0, len = multi.length; i < len; i++) {
 365                 this.appendChild(multi[i]);
 366             }
 367         }else{
 368             if(this.fireEvent("beforeappend", this.ownerTree, this, node) === false){
 369                 return false;
 370             }
 371             var index = this.childNodes.length;
 372             var oldParent = node.parentNode;
 373             // it's a move, make sure we move it cleanly
 374             if(oldParent){
 375                 if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index) === false){
 376                     return false;
 377                 }
 378                 oldParent.removeChild(node);
 379             }
 380             index = this.childNodes.length;
 381             if(index == 0){
 382                 this.setFirstChild(node);
 383             }
 384             this.childNodes.push(node);
 385             node.parentNode = this;
 386             var ps = this.childNodes[index-1];
 387             if(ps){
 388                 node.previousSibling = ps;
 389                 ps.nextSibling = node;
 390             }else{
 391                 node.previousSibling = null;
 392             }
 393             node.nextSibling = null;
 394             this.setLastChild(node);
 395             node.setOwnerTree(this.getOwnerTree());
 396             this.fireEvent("append", this.ownerTree, this, node, index);
 397             if(oldParent){
 398                 node.fireEvent("move", this.ownerTree, node, oldParent, this, index);
 399             }
 400             return node;
 401         }
 402     },
 403
 404     /**
 405      * Removes a child node from this node.
 406      * @param {Node} node The node to remove
 407      * @return {Node} The removed node
 408      */
 409     removeChild : function(node){
 410         var index = this.childNodes.indexOf(node);
 411         if(index == -1){
 412             return false;
 413         }
 414         if(this.fireEvent("beforeremove", this.ownerTree, this, node) === false){
 415             return false;
 416         }
 417
 418         // remove it from childNodes collection
 419         this.childNodes.splice(index, 1);
 420
 421         // update siblings
 422         if(node.previousSibling){
 423             node.previousSibling.nextSibling = node.nextSibling;
 424         }
 425         if(node.nextSibling){
 426             node.nextSibling.previousSibling = node.previousSibling;
 427         }
 428
 429         // update child refs
 430         if(this.firstChild == node){
 431             this.setFirstChild(node.nextSibling);
 432         }
 433         if(this.lastChild == node){
 434             this.setLastChild(node.previousSibling);
 435         }
 436
 437         node.setOwnerTree(null);
 438         // clear any references from the node
 439         node.parentNode = null;
 440         node.previousSibling = null;
 441         node.nextSibling = null;
 442         this.fireEvent("remove", this.ownerTree, this, node);
 443         return node;
 444     },
 445
 446     /**
 447      * Inserts the first node before the second node in this nodes childNodes collection.
 448      * @param {Node} node The node to insert
 449      * @param {Node} refNode The node to insert before (if null the node is appended)
 450      * @return {Node} The inserted node
 451      */
 452     insertBefore : function(node, refNode){
 453         if(!refNode){ // like standard Dom, refNode can be null for append
 454             return this.appendChild(node);
 455         }
 456         // nothing to do
 457         if(node == refNode){
 458             return false;
 459         }
 460
 461         if(this.fireEvent("beforeinsert", this.ownerTree, this, node, refNode) === false){
 462             return false;
 463         }
 464         var index = this.childNodes.indexOf(refNode);
 465         var oldParent = node.parentNode;
 466         var refIndex = index;
 467
 468         // when moving internally, indexes will change after remove
 469         if(oldParent == this && this.childNodes.indexOf(node) < index){
 470             refIndex--;
 471         }
 472
 473         // it's a move, make sure we move it cleanly
 474         if(oldParent){
 475             if(node.fireEvent("beforemove", node.getOwnerTree(), node, oldParent, this, index, refNode) === false){
 476                 return false;
 477             }
 478             oldParent.removeChild(node);
 479         }
 480         if(refIndex == 0){
 481             this.setFirstChild(node);
 482         }
 483         this.childNodes.splice(refIndex, 0, node);
 484         node.parentNode = this;
 485         var ps = this.childNodes[refIndex-1];
 486         if(ps){
 487             node.previousSibling = ps;
 488             ps.nextSibling = node;
 489         }else{
 490             node.previousSibling = null;
 491         }
 492         node.nextSibling = refNode;
 493         refNode.previousSibling = node;
 494         node.setOwnerTree(this.getOwnerTree());
 495         this.fireEvent("insert", this.ownerTree, this, node, refNode);
 496         if(oldParent){
 497             node.fireEvent("move", this.ownerTree, node, oldParent, this, refIndex, refNode);
 498         }
 499         return node;
 500     },
 501
 502     /**
 503      * Returns the child node at the specified index.
 504      * @param {Number} index
 505      * @return {Node}
 506      */
 507     item : function(index){
 508         return this.childNodes[index];
 509     },
 510
 511     /**
 512      * Replaces one child node in this node with another.
 513      * @param {Node} newChild The replacement node
 514      * @param {Node} oldChild The node to replace
 515      * @return {Node} The replaced node
 516      */
 517     replaceChild : function(newChild, oldChild){
 518         this.insertBefore(newChild, oldChild);
 519         this.removeChild(oldChild);
 520         return oldChild;
 521     },
 522
 523     /**
 524      * Returns the index of a child node
 525      * @param {Node} node
 526      * @return {Number} The index of the node or -1 if it was not found
 527      */
 528     indexOf : function(child){
 529         return this.childNodes.indexOf(child);
 530     },
 531
 532     /**
 533      * Returns the tree this node is in.
 534      * @return {Tree}
 535      */
 536     getOwnerTree : function(){
 537         // if it doesn't have one, look for one
 538         if(!this.ownerTree){
 539             var p = this;
 540             while(p){
 541                 if(p.ownerTree){
 542                     this.ownerTree = p.ownerTree;
 543                     break;
 544                 }
 545                 p = p.parentNode;
 546             }
 547         }
 548         return this.ownerTree;
 549     },
 550
 551     /**
 552      * Returns depth of this node (the root node has a depth of 0)
 553      * @return {Number}
 554      */
 555     getDepth : function(){
 556         var depth = 0;
 557         var p = this;
 558         while(p.parentNode){
 559             ++depth;
 560             p = p.parentNode;
 561         }
 562         return depth;
 563     },
 564
 565     // private
 566     setOwnerTree : function(tree){
 567         // if it's move, we need to update everyone
 568         if(tree != this.ownerTree){
 569             if(this.ownerTree){
 570                 this.ownerTree.unregisterNode(this);
 571             }
 572             this.ownerTree = tree;
 573             var cs = this.childNodes;
 574             for(var i = 0, len = cs.length; i < len; i++) {
 575                 cs[i].setOwnerTree(tree);
 576             }
 577             if(tree){
 578                 tree.registerNode(this);
 579             }
 580         }
 581     },
 582
 583     /**
 584      * Returns the path for this node. The path can be used to expand or select this node programmatically.
 585      * @param {String} attr (optional) The attr to use for the path (defaults to the node's id)
 586      * @return {String} The path
 587      */
 588     getPath : function(attr){
 589         attr = attr || "id";
 590         var p = this.parentNode;
 591         var b = [this.attributes[attr]];
 592         while(p){
 593             b.unshift(p.attributes[attr]);
 594             p = p.parentNode;
 595         }
 596         var sep = this.getOwnerTree().pathSeparator;
 597         return sep + b.join(sep);
 598     },
 599
 600     /**
 601      * Bubbles up the tree from this node, calling the specified function with each node. The scope (<i>this</i>) of
 602      * function call will be the scope provided or the current node. The arguments to the function
 603      * will be the args provided or the current node. If the function returns false at any point,
 604      * the bubble is stopped.
 605      * @param {Function} fn The function to call
 606      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 607      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 608      */
 609     bubble : function(fn, scope, args){
 610         var p = this;
 611         while(p){
 612             if(fn.call(scope || p, args || p) === false){
 613                 break;
 614             }
 615             p = p.parentNode;
 616         }
 617     },
 618
 619     /**
 620      * Cascades down the tree from this node, calling the specified function with each node. The scope (<i>this</i>) of
 621      * function call will be the scope provided or the current node. The arguments to the function
 622      * will be the args provided or the current node. If the function returns false at any point,
 623      * the cascade is stopped on that branch.
 624      * @param {Function} fn The function to call
 625      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 626      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 627      */
 628     cascade : function(fn, scope, args){
 629         if(fn.call(scope || this, args || this) !== false){
 630             var cs = this.childNodes;
 631             for(var i = 0, len = cs.length; i < len; i++) {
 632                 cs[i].cascade(fn, scope, args);
 633             }
 634         }
 635     },
 636
 637     /**
 638      * Interates the child nodes of this node, calling the specified function with each node. The scope (<i>this</i>) of
 639      * function call will be the scope provided or the current node. The arguments to the function
 640      * will be the args provided or the current node. If the function returns false at any point,
 641      * the iteration stops.
 642      * @param {Function} fn The function to call
 643      * @param {Object} scope (optional) The scope of the function (defaults to current node)
 644      * @param {Array} args (optional) The args to call the function with (default to passing the current node)
 645      */
 646     eachChild : function(fn, scope, args){
 647         var cs = this.childNodes;
 648         for(var i = 0, len = cs.length; i < len; i++) {
 649                 if(fn.call(scope || this, args || cs[i]) === false){
 650                     break;
 651                 }
 652         }
 653     },
 654
 655     /**
 656      * Finds the first child that has the attribute with the specified value.
 657      * @param {String} attribute The attribute name
 658      * @param {Mixed} value The value to search for
 659      * @return {Node} The found child or null if none was found
 660      */
 661     findChild : function(attribute, value){
 662         var cs = this.childNodes;
 663         for(var i = 0, len = cs.length; i < len; i++) {
 664                 if(cs[i].attributes[attribute] == value){
 665                     return cs[i];
 666                 }
 667         }
 668         return null;
 669     },
 670
 671     /**
 672      * Finds the first child by a custom function. The child matches if the function passed
 673      * returns true.
 674      * @param {Function} fn
 675      * @param {Object} scope (optional)
 676      * @return {Node} The found child or null if none was found
 677      */
 678     findChildBy : function(fn, scope){
 679         var cs = this.childNodes;
 680         for(var i = 0, len = cs.length; i < len; i++) {
 681                 if(fn.call(scope||cs[i], cs[i]) === true){
 682                     return cs[i];
 683                 }
 684         }
 685         return null;
 686     },
 687
 688     /**
 689      * Sorts this nodes children using the supplied sort function
 690      * @param {Function} fn
 691      * @param {Object} scope (optional)
 692      */
 693     sort : function(fn, scope){
 694         var cs = this.childNodes;
 695         var len = cs.length;
 696         if(len > 0){
 697             var sortFn = scope ? function(){fn.apply(scope, arguments);} : fn;
 698             cs.sort(sortFn);
 699             for(var i = 0; i < len; i++){
 700                 var n = cs[i];
 701                 n.previousSibling = cs[i-1];
 702                 n.nextSibling = cs[i+1];
 703                 if(i == 0){
 704                     this.setFirstChild(n);
 705                 }
 706                 if(i == len-1){
 707                     this.setLastChild(n);
 708                 }
 709             }
 710         }
 711     },
 712
 713     /**
 714      * Returns true if this node is an ancestor (at any point) of the passed node.
 715      * @param {Node} node
 716      * @return {Boolean}
 717      */
 718     contains : function(node){
 719         return node.isAncestor(this);
 720     },
 721
 722     /**
 723      * Returns true if the passed node is an ancestor (at any point) of this node.
 724      * @param {Node} node
 725      * @return {Boolean}
 726      */
 727     isAncestor : function(node){
 728         var p = this.parentNode;
 729         while(p){
 730             if(p == node){
 731                 return true;
 732             }
 733             p = p.parentNode;
 734         }
 735         return false;
 736     },
 737
 738     toString : function(){
 739         return "[Node"+(this.id?" "+this.id:"")+"]";
 740     }
 741 });