text: /*!
   * treeDiffer Namespace for treeDiffer.js
   *
   * Version 1.0.1
   * https://github.com/Tchanders/treeDiffer.js
   *
   * Released under the MIT license
   */
  
  window.treeDiffer = {};
  
  /*!
   * treeDiffer.TreeNode
   *
   * Released under the MIT license
   */
  
  /**
   * TreeNode
   *
   * Abstract TreeNode class for Trees to be diffed. It should be extended,
   * then a Tree should be built by passing the root node and the name of
   * the new class into the Tree constructor.
   *
   * @class
   * @constructor
   * @param {Object} node Object representing a node to be wrapped
   */
  treeDiffer.TreeNode = function ( node ) {
  	this.node = node;
  	this.children = [];
  	this.index = null;
  	this.leftmost = null;
  };
  
  /**
   * Add a node to the list of this node's children
   *
   * @param {treeDiffer.TreeNode} child
   */
  treeDiffer.TreeNode.prototype.addChild = function ( child ) {
  	this.children.push( child );
  	child.parent = this;
  };
  
  /**
   * Check if another TreeNode is equal to this node. Conditions for equality
   * will depend on the use case.
   */
  treeDiffer.TreeNode.prototype.isEqual = null;
  
  /**
   * Get the children of the original node wrapped by this tree node. How to
   * find and filter children will depend on the use case.
   */
  treeDiffer.TreeNode.prototype.getOriginalNodeChildren = null;
  
  /*!
   * treeDiffer.Tree
   *
   * Released under the MIT license
   */
  
  /**
   * Tree
   *
   * A group of TreeNodes connected by parent-child relationships in a tree
   * structure, along with certain properties that define the exact structure of the
   * tree: the node order, the keyroots, and the leftmost node of each node. (Terms
   * defined in: http://epubs.siam.org/doi/abs/10.1137/0218082?journalCode=smjcat)
   *
   * @class
   * @constructor
   *
   * @param {treeDiffer.TreeNode} node Root node of the tree
   * @param {Function} nodeClass Concrete subclass of treeDiffer.TreeNode
   * @param {Object} config Config options for nodeClass
   */
  treeDiffer.Tree = function ( node, nodeClass, config ) {
  
  	this.root = null;
  	this.nodeClass = nodeClass;
  	this.orderedNodes = [];
  	this.keyRoots = [];
  
  	this.findKeyRootsAndOrderedNodes( node, config );
  
  };
  
  /**
   * Find the post-ordering of the tree nodes, the keyroots and the leftmost of each
   * node.
   *
   * @param {Object} node Root node in original tree
   * @param {Object} config Config options for nodeClass
   */
  treeDiffer.Tree.prototype.findKeyRootsAndOrderedNodes = function ( node, config ) {
  	var leftmost,
  		leftmostsToKeyRoots = {},
  		tree = this;
  
  	/**
  	 * Find the tree nodes in post-order, find the leftmost of each node, and store
  	 * the order and leftmost as properties of the nodes.
  	 *
  	 * @param {treeDiffer.TreeNode} treeNode Node currently being checked
  	 * @param {Array} orderedNodes Array to be populated with nodes in order
  	 * @param {Object} leftmostsToKeyRoots Each keyroot and its leftmost
  	 */
  	function postOrderNodes( treeNode, orderedNodes, leftmostsToKeyRoots ) {
  		var i, ilen, childNode,
  			children = treeNode.getOriginalNodeChildren();
  
  		for ( i = 0, ilen = children.length; i < ilen; i++ ) {
  			// eslint-disable-next-line new-cap
  			childNode = new tree.nodeClass( children[ i ], config );
  			treeNode.addChild( childNode );
  			postOrderNodes( childNode, orderedNodes, leftmostsToKeyRoots );
  		}
  
  		// Record node order
  		orderedNodes.push( treeNode );
  		treeNode.index = orderedNodes.length - 1;
  
  		// Record index of leftmost node
  		// If this node is a leaf, it is its own leftmost
  		treeNode.leftmost = treeNode.children.length === 0 ? treeNode.index : treeNode.children[ 0 ].leftmost;
  
  		// Update the key root corresponding to this leftmost
  		// A keyroot is the higest indexed node with each leftmost
  		leftmostsToKeyRoots[ treeNode.leftmost ] = treeNode.index;
  	}
  
  	// Store the nodes in order
  	// eslint-disable-next-line new-cap
  	this.root = new tree.nodeClass( node, config );
  	this.orderedNodes = [];
  	postOrderNodes( this.root, this.orderedNodes, leftmostsToKeyRoots );
  
  	// Store the the key roots in order of node index
  	for ( leftmost in leftmostsToKeyRoots ) {
  		this.keyRoots.push( leftmostsToKeyRoots[ leftmost ] );
  	}
  	this.keyRoots.sort( function ( a, b ) {
  		return a - b;
  	} );
  
  };
  
  /**
   * Get all the descendants of a node
   *
   * @param {treeDiffer.TreeNode} node Node whose descendants to find
   * @return {Array} Descendants of the node
   */
  treeDiffer.Tree.prototype.getNodeDescendants = function ( node ) {
  	var descendants = [];
  
  	function addDescendants( parentNode ) {
  		var i, ilen, childNode;
  		for ( i = 0, ilen = parentNode.children.length; i < ilen; i++ ) {
  			childNode = parentNode.children[ i ];
  			descendants.push( childNode );
  			addDescendants( childNode );
  		}
  	}
  
  	addDescendants( node );
  
  	return descendants;
  };
  
  /*!
   * treeDiffer.Differ
   *
   * Released under the MIT license
   */
  
  // eslint-disable dot-notation
  // We use [ 'null' ] as an index, but for consistencty with
  // variable indicies [ i ][ j ] we prefer not to use dot notation
  
  /**
   * Differ
   *
   * Find the minimum transactions to get from the first tree to the second tree. Each
   * transaction is of the form [nodeToRemove, nodeToInsert], where nodeToRemove or
   * nodeToInsert (but not both) can be null. The tree diffing algorithm is presented in:
   * http://epubs.siam.org/doi/abs/10.1137/0218082?journalCode=smjcat
   *
   * @class
   * @constructor
   * @param {treeDiffer.Tree} tree1 First tree
   * @param {treeDiffer.Tree} tree2 Second tree
   * @param {Number} [timeout=1000] Timeout after which to stop diffing
   */
  treeDiffer.Differ = function ( tree1, tree2, timeout ) {
  	var i, ilen, j, jlen, transactions,
  		transactionIndex = 0;
  
  	this.endTime = new Date().getTime() + ( timeout || 1000 );
  
  	this.tree1 = tree1;
  	this.tree2 = tree2;
  
  	this.insertCost = 1;
  	this.removeCost = 1;
  	this.changeCost = 1;
  
  	// Temporary, changing store of transactions
  	transactions = {
  		'null': {
  			'null': []
  		}
  	};
  
  	// Permanent store of transactions such that transactions[x][y] is the minimum
  	// transactions to get from the sub-tree rooted at node x (in tree1) to the sub-tree
  	// rooted at node y (in tree2).
  	this.transactions = {
  		'null': {}
  	};
  
  	// All possible transactions
  	this.indexToTransaction = [];
  	this.indexToTransaction.push( [ null, null ] );
  
  	// Indices for each transaction, to avoid high performance cost of creating the
  	// transactions multiple times
  	this.transactionToIndex = {
  		'null': {
  			'null': 0
  		}
  	};
  	transactionIndex += 1;
  
  	// Populate transaction stores
  	for ( i = 0, ilen = this.tree1.orderedNodes.length; i < ilen; i++ ) {
  
  		transactions[ i ] = {
  			'null': []
  		};
  		this.transactionToIndex[ i ] = {
  			'null': transactionIndex
  		};
  		transactionIndex += 1;
  		this.indexToTransaction.push( [ i, null ] );
  
  		for ( j = 0, jlen = this.tree2.orderedNodes.length; j < jlen; j++ ) {
  			transactions[ null ][ j ] = [];
  			transactions[ i ][ j ] = [];
  
  			this.transactionToIndex[ null ][ j ] = transactionIndex;
  			transactionIndex += 1;
  			this.indexToTransaction.push( [ null, j ] );
  
  			this.transactionToIndex[ i ][ j ] = transactionIndex;
  			transactionIndex += 1;
  			this.indexToTransaction.push( [ i, j ] );
  		}
  
  		this.transactions[ i ] = {};
  
  	}
  
  	this.populateTransactions( transactions );
  };
  
  /**
   * Populate this.transactions with minimum transactions between all possible trees
   *
   * @param {Object} transactions Temporary store of transactions between trees
   */
  treeDiffer.Differ.prototype.populateTransactions = function ( transactions ) {
  	var i, ilen, j, jlen, iNulls, jNulls, ii, jj, keyRoot1, keyRoot2,
  		differ = this;
  
  	function getTransactionFromIndex( index ) {
  		return differ.indexToTransaction[ index ];
  	}
  
  	for ( i = 0, ilen = this.tree1.keyRoots.length; i < ilen; i++ ) {
  
  		// Make transactions for tree -> null
  		keyRoot1 = this.tree1.orderedNodes[ this.tree1.keyRoots[ i ] ];
  		iNulls = [];
  		for ( ii = keyRoot1.leftmost; ii < keyRoot1.index + 1; ii++ ) {
  			iNulls.push( this.transactionToIndex[ ii ][ null ] );
  			transactions[ ii ][ null ] = iNulls.slice();
  		}
  
  		for ( j = 0, jlen = this.tree2.keyRoots.length; j < jlen; j++ ) {
  
  			// Make transactions of null -> tree
  			keyRoot2 = this.tree2.orderedNodes[ this.tree2.keyRoots[ j ] ];
  			jNulls = [];
  			for ( jj = keyRoot2.leftmost; jj < keyRoot2.index + 1; jj++ ) {
  				jNulls.push( this.transactionToIndex[ null ][ jj ] );
  				transactions[ null ][ jj ] = jNulls.slice();
  			}
  
  			// Get the diff
  			this.findMinimumTransactions( keyRoot1, keyRoot2, iNulls, jNulls, transactions );
  
  			if ( new Date().getTime() > this.endTime ) {
  				this.transactions = null;
  				return;
  			}
  		}
  	}
  
  	for ( i = 0, ilen = this.tree1.orderedNodes.length; i < ilen; i++ ) {
  		for ( j = 0, jlen = this.tree2.orderedNodes.length; j < jlen; j++ ) {
  			if ( this.transactions[ i ][ j ] && this.transactions[ i ][ j ].length > 0 ) {
  				this.transactions[ i ][ j ] = this.transactions[ i ][ j ].map( getTransactionFromIndex );
  			}
  		}
  	}
  
  };
  
  /**
   * Get the cost of removing a node from the first tree, inserting a node into the second
   * tree, or relabelling a node from the first tree to a node from the second tree.
   *
   * @param {treeDiffer.TreeNode} node1 Node from the first tree
   * @param {treeDiffer.TreeNode} node2 Node from the second tree]
   * @return {number} Cost of the transaction
   */
  treeDiffer.Differ.prototype.getNodeDistance = function ( node1, node2 ) {
  	if ( node1 === null && node2 === null ) {
  		return 0;
  	}
  	if ( node1 === null ) {
  		return this.insertCost;
  	}
  	if ( node2 === null ) {
  		return this.removeCost;
  	}
  	if ( node1.isEqual( node2 ) ) {
  		return 0;
  	}
  	return this.changeCost;
  };
  
  /**
   * Find the minimum transactions to get from the first tree to the second tree. This
   * method is the heart of the tree differ.
   *
   * @param {treeDiffer.TreeNode} keyRoot1 A keyroot from the first tree
   * @param {treeDiffer.TreeNode} keyRoot2 A keyroot from the second tree
   * @param {Object} iNulls Transactions from all relevant sub-trees to the null tree
   * @param {Object} jNulls Transactions from the null tree to all relevant sub-trees
   * @param {Object} transactions Temporary store of transactions between trees
   */
  treeDiffer.Differ.prototype.findMinimumTransactions = function ( keyRoot1, keyRoot2, iNulls, jNulls, transactions ) {
  	var i, j, iMinus1, jMinus1, costs, nodeDistance, transaction, remove, insert, change;
  
  	for ( i = keyRoot1.leftmost; i < keyRoot1.index + 1; i++ ) {
  		iMinus1 = i === keyRoot1.leftmost ? null : i - 1;
  
  		for ( j = keyRoot2.leftmost; j < keyRoot2.index + 1; j++ ) {
  			jMinus1 = j === keyRoot2.leftmost ? null : j - 1;
  
  			if ( this.tree1.orderedNodes[ i ].leftmost === keyRoot1.leftmost && this.tree2.orderedNodes[ j ].leftmost === keyRoot2.leftmost ) {
  
  				// Previous transactions, leading up to a remove, insert or change
  				remove = transactions[ iMinus1 ][ j ];
  				insert = transactions[ i ][ jMinus1 ];
  				change = transactions[ iMinus1 ][ jMinus1 ];
  
  				nodeDistance = this.getNodeDistance( this.tree1.orderedNodes[ i ], this.tree2.orderedNodes[ j ] );
  
  				// Cost of each transaction
  				costs = [
  					remove.length + this.removeCost,
  					insert.length + this.insertCost,
  					change.length + nodeDistance
  				];
  
  				transaction = costs.indexOf( Math.min.apply( null, costs ) );
  				if ( transaction === 0 ) {
  					// Record a remove
  					( transactions[ i ][ j ] = remove.slice() ).push(
  						this.transactionToIndex[ i ][ null ]
  					);
  				} else if ( transaction === 1 ) {
  					// Record an insert
  					( transactions[ i ][ j ] = insert.slice() ).push(
  						this.transactionToIndex[ null ][ j ]
  					);
  				} else {
  					transactions[ i ][ j ] = change.slice();
  					// If nodes i and j are different, record a change,
  					// otherwise there is no transaction
  					if ( nodeDistance === 1 ) {
  						transactions[ i ][ j ].push( this.transactionToIndex[ i ][ j ] );
  					}
  				}
  
  				this.transactions[ i ][ j ] = transactions[ i ][ j ].slice();
  			} else {
  
  				// Previous transactions, leading up to a remove, insert or change
  				remove = transactions[ iMinus1 ][ j ];
  				insert = transactions[ i ][ jMinus1 ];
  				change = transactions[
  					this.tree1.orderedNodes[ i ].leftmost - 1 < keyRoot1.leftmost ? null : this.tree1.orderedNodes[ i ].leftmost - 1
  				][
  					this.tree2.orderedNodes[ j ].leftmost - 1 < keyRoot2.leftmost ? null : this.tree2.orderedNodes[ j ].leftmost - 1
  				];
  
  				costs = [
  					remove.length + this.removeCost,
  					insert.length + this.insertCost,
  					change.length + this.transactions[ i ][ j ].length
  				];
  
  				transaction = costs.indexOf( Math.min.apply( null, costs ) );
  				if ( transaction === 0 ) {
  					// Record a remove
  					( transactions[ i ][ j ] = remove.slice() ).push(
  						this.transactionToIndex[ i ][ null ]
  					);
  				} else if ( transaction === 1 ) {
  					// Record an insert
  					( transactions[ i ][ j ] = insert.slice() ).push(
  						this.transactionToIndex[ null ][ j ]
  					);
  				} else {
  					// Record a change
  					transactions[ i ][ j ] = change.concat( this.transactions[ i ][ j ] );
  				}
  
  			}
  
  		}
  
  	}
  };
  
  /**
   * Given a set of transactions and the lengths of two trees, find the nodes that
   * correspond.
   *
   * @param {Array} transactions Minimum transactions to get from the first tree to the
   * second tree
   * @param {number} oldTreeLength Number of nodes in the first tree
   * @param {number} newTreeLength Number of nodes in the second tree
   * @return {Object} Corresponding nodes
   */
  treeDiffer.Differ.prototype.getCorrespondingNodes = function ( transactions, oldTreeLength, newTreeLength ) {
  	var i, j, rem, ins,
  		oldToNew = {},
  		newToOld = {},
  		remove = [],
  		insert = [],
  		change = {},
  		ilen = Math.max( oldTreeLength, newTreeLength ),
  		jlen = ilen;
  
  	for ( i = 0; i < transactions.length; i++ ) {
  		if ( transactions[ i ][ 0 ] === null ) {
  			insert.push( transactions[ i ][ 1 ] );
  		} else if ( transactions[ i ][ 1 ] === null ) {
  			remove.push( transactions[ i ][ 0 ] );
  		} else {
  			oldToNew[ transactions[ i ][ 0 ] ] = transactions[ i ][ 1 ];
  			newToOld[ transactions[ i ][ 1 ] ] = transactions[ i ][ 0 ];
  			change[ transactions[ i ][ 0 ] ] = transactions[ i ][ 1 ];
  		}
  	}
  
  	rem = remove.slice();
  	ins = insert.slice();
  
  	remove.sort( function ( a, b ) { return a - b; } );
  	insert.sort( function ( a, b ) { return a - b; } );
  
  	for ( i = 0, j = 0; i < ilen && j < jlen; i++, j++ ) {
  		if ( i === remove[ 0 ] ) {
  			// Old node is a remove
  			remove.shift();
  			j--;
  		} else if ( j === insert[ 0 ] ) {
  			// New node is an insert
  			insert.shift();
  			i--;
  		} else if ( !( i in oldToNew ) && !( j in newToOld ) ) {
  			// Neither is changed, so they must correspond
  			// NB Moves don't exist to the tree differ
  			oldToNew[ i ] = j;
  			newToOld[ j ] = i;
  		} else if ( !( i in oldToNew ) ) {
  			// Old node is unchanged, new node is changed
  			i--;
  		} else if ( !( j in newToOld ) ) {
  			// New node is unchanged, old node is changed
  			j--;
  		}
  	}
  
  	return {
  		oldToNew: oldToNew,
  		newToOld: newToOld,
  		remove: rem,
  		insert: ins,
  		change: change
  	};
  };
  