| Index: trunk/extensions/VisualEditor/tests/es/es.DocumentNode.test.js |
| — | — | @@ -0,0 +1,46 @@ |
| | 2 | +module( 'es/bases' ); |
| | 3 | + |
| | 4 | +test( 'es.DocumentNode.getCommonAncestorPaths', 14, function() { |
| | 5 | + var documentModel = es.DocumentModel.newFromPlainObject( esTest.obj ), result; |
| | 6 | + |
| | 7 | + var list = documentModel.children[1].children[0].children[0].children[1]; |
| | 8 | + result = es.DocumentNode.getCommonAncestorPaths( list, list ); |
| | 9 | + // Test 1 |
| | 10 | + ok( result.commonAncestor == list, 'same nodes (commonAncestor)' ); |
| | 11 | + // Test 2 |
| | 12 | + ok( es.compareArrays( result.node1Path, [] ), 'adjacent list items (node1Path)' ); |
| | 13 | + // Test 3 |
| | 14 | + ok( es.compareArrays( result.node2Path, [] ), 'adjacent list items (node2Path)' ); |
| | 15 | + |
| | 16 | + result = es.DocumentNode.getCommonAncestorPaths( list.children[0], list.children[1] ); |
| | 17 | + // Test 4 |
| | 18 | + ok( result.commonAncestor == list, 'adjacent list items (commonAncestor)' ); |
| | 19 | + // Test 5 |
| | 20 | + ok( es.compareArrays( result.node1Path, [ list.children[0] ] ), 'adjacent list items (node1Path)' ); |
| | 21 | + // Test 6 |
| | 22 | + ok( es.compareArrays( result.node2Path, [ list.children[1] ] ), 'adjacent list items (node2Path)' ); |
| | 23 | + |
| | 24 | + result = es.DocumentNode.getCommonAncestorPaths( list.children[0], list.children[2] ); |
| | 25 | + // Test 7 |
| | 26 | + ok( result.commonAncestor == list, 'non-adjacent sibling list items (commonAncestor)' ); |
| | 27 | + // Test 8 |
| | 28 | + ok( es.compareArrays( result.node1Path, [ list.children[0] ] ), 'non-adjacent sibling list items (node1Path)' ); |
| | 29 | + // Test 9 |
| | 30 | + ok( es.compareArrays( result.node2Path, [ list.children[2] ] ), 'non-adjacent sibling list items (node2Path)' ); |
| | 31 | + |
| | 32 | + result = es.DocumentNode.getCommonAncestorPaths( list.children[0].children[0], list.children[2].children[0] ); |
| | 33 | + // Test 10 |
| | 34 | + ok( result.commonAncestor == list, 'paragraphs inside list items (commonAncestor)' ); |
| | 35 | + // Test 11 |
| | 36 | + ok( es.compareArrays( result.node1Path, [ list.children[0].children[0], list.children[0] ] ), 'paragraphs inside list items (node1Path)' ); |
| | 37 | + // Test 12 |
| | 38 | + ok( es.compareArrays( result.node2Path, [ list.children[2].children[0], list.children[2] ] ), 'paragraphs inside list items (node2Path)' ); |
| | 39 | + |
| | 40 | + result = es.DocumentNode.getCommonAncestorPaths( list.children[0].children[0], list.children[2] ); |
| | 41 | + // Test 13 |
| | 42 | + equal( result, false, 'nodes of unequal depth' ); |
| | 43 | + |
| | 44 | + result = es.DocumentNode.getCommonAncestorPaths( list, es.DocumentModel.newFromPlainObject( esTest.obj ).children[1] ); |
| | 45 | + // Test 14 |
| | 46 | + equal( result, false, 'nodes in different trees' ); |
| | 47 | +} ); |
| \ No newline at end of file |
| Property changes on: trunk/extensions/VisualEditor/tests/es/es.DocumentNode.test.js |
| ___________________________________________________________________ |
| Added: svn:eol-style |
| 1 | 48 | + native |
| Index: trunk/extensions/VisualEditor/tests/es/index.html |
| — | — | @@ -46,5 +46,6 @@ |
| 47 | 47 | <script src="es.DocumentBranchNode.test.js"></script> |
| 48 | 48 | <script src="es.DocumentModelBranchNode.test.js"></script> |
| 49 | 49 | <script src="es.DocumentModel.test.js"></script> |
| | 50 | + <script src="es.DocumentNode.test.js"></script> |
| 50 | 51 | </body> |
| 51 | 52 | </html> |
| Index: trunk/extensions/VisualEditor/modules/es/bases/es.DocumentNode.js |
| — | — | @@ -69,6 +69,40 @@ |
| 70 | 70 | } |
| 71 | 71 | }; |
| 72 | 72 | |
| | 73 | +/** |
| | 74 | + * Find the common ancestor of two equal-depth nodes, and return the |
| | 75 | + * path from each node to the common ancestor. |
| | 76 | + * @param {es.DocumentNode} node1 |
| | 77 | + * @param {es.DocumentNode} node2 |
| | 78 | + * @returns {Object|Boolean} Object with keys 'commonAncestor', 'node1Path' and 'node2Path', |
| | 79 | + * or false if there is no common ancestor or if the nodes have unequal depth |
| | 80 | + */ |
| | 81 | +es.DocumentNode.getCommonAncestorPaths = function( node1, node2 ) { |
| | 82 | + var path1 = [], |
| | 83 | + path2 = [], |
| | 84 | + n1 = node1, |
| | 85 | + n2 = node2; |
| | 86 | + |
| | 87 | + // Move up from n1 and n2 simultaneously until we find the |
| | 88 | + // common ancestor |
| | 89 | + while ( n1 !== n2 ) { |
| | 90 | + // Add these nodes to their respective paths |
| | 91 | + path1.push( n1 ); |
| | 92 | + path2.push( n2 ); |
| | 93 | + // Move up |
| | 94 | + n1 = n1.getParent(); |
| | 95 | + n2 = n2.getParent(); |
| | 96 | + if ( n1 === null || n2 === null ) { |
| | 97 | + // Reached a root, so no common ancestor or unequal depth |
| | 98 | + return false; |
| | 99 | + } |
| | 100 | + } |
| | 101 | + |
| | 102 | + // If we got here, we've found the common ancestor, and because we did |
| | 103 | + // simultaneous traversal we also know node1 and node2 have the same depth. |
| | 104 | + return { 'commonAncestor': n1, 'node1Path': path1, 'node2Path': path2 }; |
| | 105 | +}; |
| | 106 | + |
| 73 | 107 | /* Inheritance */ |
| 74 | 108 | |
| 75 | 109 | es.extendClass( es.DocumentNode, es.EventEmitter ); |