{"size": 3864, "ext": "js", "max_stars_repo_path": "source/core/utils/struct/TreeUtils.js", "max_stars_repo_name": "j2l/nunuStudio", "max_stars_repo_stars_event_min_datetime": "2016-09-06T00:40:46.000Z", "max_stars_repo_stars_event_max_datetime": "2022-03-30T07:00:13.000Z", "max_issues_repo_path": "source/core/utils/struct/TreeUtils.js", "max_issues_repo_name": "j2l/nunuStudio", "max_issues_repo_issues_event_min_datetime": "2017-02-06T17:10:02.000Z", "max_issues_repo_issues_event_max_datetime": "2022-03-30T03:52:22.000Z", "max_forks_repo_path": "source/core/utils/struct/TreeUtils.js", "max_forks_repo_name": "j2l/nunuStudio", "max_forks_repo_forks_event_min_datetime": "2016-10-09T00:24:35.000Z", "max_forks_repo_forks_event_max_datetime": "2022-03-30T04:24:42.000Z"}
{"max_stars_count": 1663, "max_issues_count": 509, "max_forks_count": 279, "avg_line_length": 22.8639053254, "max_line_length": 131, "alphanum_fraction": 0.6428571429}
import {Tree} from "./Tree.js";

/**
 * TreeUtils used to compare Tree.
 *
 * Can also be used to compare Object structure.
 *
 * @static
 * @class TreeUtils
 */
function TreeUtils() {}

/**
 * Flag used to indicate ADDED diff.
 *
 * @attribute DIFF_ADDED
 * @type {number}
 */
TreeUtils.DIFF_ADDED = 0;

/**
 * Flag used to indicate REMOVED diff.
 *
 * @attribute DIFF_REMOVED
 * @type {number}
 */
TreeUtils.DIFF_REMOVED = 1;

/**
 * Flag used to indicate MOVED diff.
 *
 * @attribute DIFF_MOVED
 * @type {number}
 */
TreeUtils.DIFF_MOVED = 2;

/**
 * Compare two trees and return list of changes.
 *
 * oldTree is compared to newTree. The list of changes indicate wath needs to be changed in oldTree to become wqual to the newTree.
 *
 * Elements inside Trees are compared using their UUID.
 *
 * The array returned from this method contains objects in the format {status:<Operation>, uuid: <UUID>, from: <Tree>, to: <Tree>}
 *
 * @static
 * @method compare
 * @param {Tree} oldTree Old version of Tree.
 * @param {Tree} newTree New version of Tree.
 * @param {Array} diffs Recursive parameter (optional).
 * @param {Array} pathOldTree Recursive parameter (optional).
 * @param {Array} pathNewTree Recursive parameter (optional).
 * @return {Array} Array with diffs between oldTree and newTree.
 */
TreeUtils.compare = function(oldTree, newTree, diffs, pathOldTree, pathNewTree)
{
	// Differences array
	if (diffs === undefined)
	{
		diffs = [];
	}

	// Path to this tree point in positions
	if (pathOldTree === undefined)
	{
		pathOldTree = [];
	}
	if (pathNewTree === undefined)
	{
		pathNewTree = [];
	}

	var oldChildren = oldTree.children;
	var oldLength = oldChildren.length;

	var newChildren = newTree.children;
	var newLength = newChildren.length;

	var i = 0, j = 0;

	while (i < oldLength && j < newLength)
	{
		// Different element
		if (oldChildren[i].uuid !== newChildren[j].uuid)
		{
			// Element removed
			if (i + 1 < oldLength && oldChildren[i + 1].uuid === newChildren[j].uuid)
			{
				var from = pathOldTree.slice(0);
				from.push(i);

				diffs.push({status: TreeUtils.DIFF_REMOVED, uuid: oldChildren[i].uuid, from: from, to: null});
				i++;
			}
			// Element added
			else if (j + 1 < newLength && oldChildren[i].uuid === newChildren[j + 1].uuid)
			{
				var to = pathNewTree.slice(0);
				to.push(j);

				diffs.push({status: TreeUtils.DIFF_ADDED, uuid: newChildren[j].uuid, from: null, to: to});
				j++;
			}
		}

		// If element is the same compare its children
		if (oldChildren[i].uuid === newChildren[j].uuid)
		{
			var from = pathOldTree.slice(0);
			from.push(i);

			var to = pathNewTree.slice(0);
			to.push(j);

			TreeUtils.compare(oldChildren[i], newChildren[j], diffs, from, to);
		}

		i++;
		j++;
	}

	// Remaining elements missing in A
	while (i < oldLength)
	{
		var from = pathOldTree.slice(0);
		from.push(i);

		diffs.push({status: TreeUtils.DIFF_REMOVED, uuid: oldChildren[i].uuid, from: from, to: null});
		i++;
	}

	// Extra elements added in B
	while (j < newLength)
	{
		var to = pathNewTree.slice(0);
		to.push(j);

		diffs.push({status: TreeUtils.DIFF_ADDED, uuid: newChildren[j].uuid, from: null, to: to});
		j++;
	}

	// Check if some elements have removed and added status at same time
	for (var i = 0; i < diffs.length; i++)
	{
		for (var j = 0; j < diffs.length; j++)
		{
			if (diffs[i].uuid === diffs[j].uuid)
			{
				if (diffs[i].status === TreeUtils.DIFF_REMOVED && diffs[j].status === TreeUtils.DIFF_ADDED)
				{
					diffs[i].status = TreeUtils.DIFF_MOVED;
					diffs[i].to = diffs[j].to;
					diffs.splice(j, 1);
				}
				else if (diffs[j].status === TreeUtils.DIFF_REMOVED && diffs[i].status === TreeUtils.DIFF_ADDED)
				{
					diffs[i].status = TreeUtils.DIFF_MOVED;
					diffs[i].from = diffs[j].from;
					diffs.splice(j, 1);
				}
			}
		}
	}

	return diffs;
};

export {TreeUtils};
