| Index: trunk/extensions/VisualEditor/modules/es/bases/es.DocumentBranchNode.js |
| — | — | @@ -45,21 +45,69 @@ |
| 46 | 46 | * @param {Boolean} [reverse] Whether to iterate backwards |
| 47 | 47 | */ |
| 48 | 48 | es.DocumentBranchNode.prototype.traverseLeafNodes = function( callback, from, reverse ) { |
| 49 | | - // TODO: Implement from and reverse |
| 50 | | - // TODO: We'll need an iterative rather than recursive implementation for from, probably |
| 51 | | - var i, childNode, callbackResult; |
| 52 | | - for ( i = reverse ? this.children.length - 1 : 0; reverse ? i >= 0 : i < this.children.length; reverse ? i-- : i++ ) { |
| 53 | | - childNode = this.children[i]; |
| | 49 | + var indexStack = [], index = 0, node = this, childNode, callbackResult, n, p, i; |
| | 50 | + |
| | 51 | + if ( from !== undefined ) { |
| | 52 | + // Reverse-engineer the index stack by starting at from and |
| | 53 | + // working our way up until we reach this |
| | 54 | + n = from; |
| | 55 | + while ( n !== this ) { |
| | 56 | + p = n.getParent(); |
| | 57 | + if ( !p ) { |
| | 58 | + // n is a root node and we haven't reached this |
| | 59 | + // That means from isn't a descendant of this |
| | 60 | + throw "from parameter passed to traverseLeafNodes() must be a descendant"; |
| | 61 | + } |
| | 62 | + // Find the index of n in p |
| | 63 | + i = es.arrayIndexOf( p.getChildren(), n ); |
| | 64 | + if ( i === -1 ) { |
| | 65 | + // This isn't supposed to be possible |
| | 66 | + throw "Tree corruption detected: node isn't in its parent's children array"; |
| | 67 | + } |
| | 68 | + indexStack.push( i ); |
| | 69 | + // Move up |
| | 70 | + n = p; |
| | 71 | + } |
| | 72 | + // We've built the indexStack in reverse order, so reverse it |
| | 73 | + indexStack = indexStack.reverse(); |
| | 74 | + |
| | 75 | + // Set up the variables such that from will be visited next |
| | 76 | + index = indexStack.pop(); |
| | 77 | + node = from.getParent(); // from is a descendant of this so its parent exists |
| | 78 | + } |
| | 79 | + |
| | 80 | + while ( true ) { |
| | 81 | + childNode = node.children[index]; |
| | 82 | + if ( childNode === undefined ) { |
| | 83 | + if ( indexStack.length > 0 ) { |
| | 84 | + // We're done traversing the current node, move back out of it |
| | 85 | + node = node.getParent(); |
| | 86 | + index = indexStack.pop(); |
| | 87 | + // Move to the next child |
| | 88 | + index++; |
| | 89 | + continue; |
| | 90 | + } else { |
| | 91 | + // We can't move up any more, so we're done |
| | 92 | + return; |
| | 93 | + } |
| | 94 | + } |
| | 95 | + |
| 54 | 96 | if ( childNode.hasChildren() ) { |
| 55 | | - // Recurse |
| 56 | | - childNode.traverseLeafNodes( callback, from, reverse ); |
| | 97 | + // Descend into this node |
| | 98 | + node = childNode; |
| | 99 | + // Push our current index onto the stack |
| | 100 | + indexStack.push( index ); |
| | 101 | + // Set the current index to zero |
| | 102 | + index = 0; |
| 57 | 103 | } else { |
| 58 | | - // It's a leaf node |
| 59 | | - callbackResult = callback( childNode /*, TODO what is index? */ ); |
| | 104 | + // This is a leaf node, visit it |
| | 105 | + callbackResult = callback( childNode ); // TODO what is index? |
| 60 | 106 | if ( callbackResult === false ) { |
| 61 | 107 | // The callback is telling us to stop |
| 62 | 108 | return; |
| 63 | 109 | } |
| | 110 | + // Move to the next child |
| | 111 | + index++; |
| 64 | 112 | } |
| 65 | 113 | } |
| 66 | 114 | }; |