bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/dtree/AbstractDataTreeNode.java - platform/eclipse.platform.resources - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2014 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *     Thomas Wolf (Paranor AG) -- optimize assembleWith
  *******************************************************************************/
 package org.eclipse.core.internal.dtree;

 import org.eclipse.core.internal.utils.Messages;
 import org.eclipse.core.internal.utils.StringPool;
 import org.eclipse.core.runtime.IPath;
 import org.eclipse.osgi.util.NLS;

 /**
  * This class and its subclasses are used to represent nodes of AbstractDataTrees.
  * Refer to the DataTree API comments for more details.
  * @see AbstractDataTree
  */
 public abstract class AbstractDataTreeNode {
 	/**
 	 * Singleton indicating no children.
 	 */
 	static final AbstractDataTreeNode[] NO_CHILDREN = new AbstractDataTreeNode[0];
 	protected AbstractDataTreeNode children[];
 	protected String name;

 	/* Node types for comparison */
 	public static final int T_COMPLETE_NODE = 0;
 	public static final int T_DELTA_NODE = 1;
 	public static final int T_DELETED_NODE = 2;
 	public static final int T_NO_DATA_DELTA_NODE = 3;

 	/**
 	 * Creates a new data tree node
 	 *
 	 * @param name
 	 *	name of new node
 	 * @param children
 	 *	children of the new node
 	 */
 	AbstractDataTreeNode(String name, AbstractDataTreeNode[] children) {
 		this.name = name;
 		if (children == null || children.length == 0)
 			this.children = AbstractDataTreeNode.NO_CHILDREN;
 		else
 			this.children = children;
 	}

 	/**
 	 * Returns a node which if applied to the receiver will produce
 	 * the corresponding node in the given parent tree.
 	 *
 	 * @param myTree  tree to which the node belongs
 	 * @param parentTree  parent tree on which to base backward delta
 	 * @param key  key of node in its tree
 	 */
 	abstract AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key);

 	/**
 	 * If this node is a node in a comparison tree, this method reverses
 	 * the comparison for this node and all children
 	 */
 	AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
 		return this;
 	}

 	/**
 	 * Returns the result of assembling nodes with the given forward delta nodes.
 	 * Both arrays must be sorted by name.
 	 * The result is sorted by name.
 	 * If keepDeleted is true, explicit representations of deletions are kept,
 	 * otherwise nodes to be deleted are removed in the result.
 	 */
 	static AbstractDataTreeNode[] assembleWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, boolean keepDeleted) {

 		// Optimize the common case where the new list is empty.
 		if (newNodes.length == 0)
 			return oldNodes;

 		// Can't just return newNodes if oldNodes has length 0
 		// because newNodes may contain deleted nodes.

 		AbstractDataTreeNode[] resultNodes = new AbstractDataTreeNode[oldNodes.length + newNodes.length];

 		// do a merge
 		int oldIndex = 0;
 		int newIndex = 0;
 		int resultIndex = 0;
 		while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
 			int log2 = 31 - Integer.numberOfLeadingZeros(oldNodes.length - oldIndex);
 			if (log2 > 1 && (newNodes.length - newIndex) <= (oldNodes.length - oldIndex) / log2) {
 				// We can expect to fare better using binary search. In particular, this will optimize the case of a folder refresh (new linked
 				// folder with many files in a flat hierarchy), where this is called repeatedly, with oldNodes containing the files added so far,
 				// and newNodes containing exactly one new node for the next file to be added. The old algorithm has quadratic performance
 				// (O((n+1)*n/2); number of string comparisons is the dominating component here) in this case; this new algorithm does O(n*log(n))
 				// string comparisons.
 				String key = newNodes[newIndex].name;
 				// Figure out where to insert the next new node.
 				int left = oldIndex;
 				int right = oldNodes.length - 1;
 				boolean found = false;
 				while (left <= right) {
 					int mid = (left + right) / 2;
 					int compare = key.compareTo(oldNodes[mid].name);
 					if (compare < 0) {
 						right = mid - 1;
 					} else if (compare > 0) {
 						left = mid + 1;
 					} else {
 						left = mid;
 						found = true;
 						break;
 					}
 				}
 				// Now copy oldNodes from oldIndex to left-1, insert the new node, increment newIndex
 				int toCopy = left - oldIndex;
 				System.arraycopy(oldNodes, oldIndex, resultNodes, resultIndex, toCopy);
 				resultIndex += toCopy;
 				if (found) {
 					AbstractDataTreeNode node = oldNodes[left++].assembleWith(newNodes[newIndex++]);
 					if (node != null && (!node.isDeleted() || keepDeleted)) {
 						resultNodes[resultIndex++] = node;
 					}
 				} else {
 					AbstractDataTreeNode node = newNodes[newIndex++];
 					if (!node.isDeleted() || keepDeleted) {
 						resultNodes[resultIndex++] = node;
 					}
 				}
 				oldIndex = left;
 			} else {
 				int compare = oldNodes[oldIndex].name.compareTo(newNodes[newIndex].name);
 				if (compare == 0) {
 					AbstractDataTreeNode node = oldNodes[oldIndex++].assembleWith(newNodes[newIndex++]);
 					if (node != null && (!node.isDeleted() || keepDeleted)) {
 						resultNodes[resultIndex++] = node;
 					}
 				} else if (compare < 0) {
 					resultNodes[resultIndex++] = oldNodes[oldIndex++];
 				} else if (compare > 0) {
 					AbstractDataTreeNode node = newNodes[newIndex++];
 					if (!node.isDeleted() || keepDeleted) {
 						resultNodes[resultIndex++] = node;
 					}
 				}
 			}
 		}
 		while (oldIndex < oldNodes.length) {
 			resultNodes[resultIndex++] = oldNodes[oldIndex++];
 		}
 		while (newIndex < newNodes.length) {
 			AbstractDataTreeNode resultNode = newNodes[newIndex++];
 			if (!resultNode.isDeleted() || keepDeleted) {
 				resultNodes[resultIndex++] = resultNode;
 			}
 		}

 		// trim size of result
 		if (resultIndex < resultNodes.length) {
 			System.arraycopy(resultNodes, 0, resultNodes = new AbstractDataTreeNode[resultIndex], 0, resultIndex);
 		}
 		return resultNodes;
 	}

 	/**
 	 * Returns the result of assembling this node with the given forward delta node.
 	 */
 	AbstractDataTreeNode assembleWith(AbstractDataTreeNode node) {

 		// If not a delta, or if the old node was deleted,
 		// then the new node represents the complete picture.
 		if (!node.isDelta() || this.isDeleted()) {
 			return node;
 		}

 		// node must be either a DataDeltaNode or a NoDataDeltaNode
 		if (node.hasData()) {
 			if (this.isDelta()) {
 				// keep deletions because they still need
 				// to hide child nodes in the parent.
 				AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
 				return new DataDeltaNode(name, node.getData(), assembledChildren);
 			}
 			// This is a complete picture, so deletions
 			// wipe out the child and are no longer useful
 			AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
 			return new DataTreeNode(name, node.getData(), assembledChildren);
 		}
 		if (this.isDelta()) {
 			AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
 			if (this.hasData())
 				return new DataDeltaNode(name, this.getData(), assembledChildren);
 			return new NoDataDeltaNode(name, assembledChildren);
 		}
 		AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
 		return new DataTreeNode(name, this.getData(), assembledChildren);
 	}

 	/**
 	 * Returns the result of assembling this node with the given forward delta node.
 	 */
 	AbstractDataTreeNode assembleWith(AbstractDataTreeNode node, IPath key, int keyIndex) {

 		// leaf case
 		int keyLen = key.segmentCount();
 		if (keyIndex == keyLen) {
 			return assembleWith(node);
 		}

 		// non-leaf case
 		int childIndex = indexOfChild(key.segment(keyIndex));
 		if (childIndex >= 0) {
 			AbstractDataTreeNode copy = copy();
 			copy.children[childIndex] = children[childIndex].assembleWith(node, key, keyIndex + 1);
 			return copy;
 		}

 		// Child not found.  Build up NoDataDeltaNode hierarchy for rest of key
 		// and assemble with that.
 		for (int i = keyLen - 2; i >= keyIndex; --i) {
 			node = new NoDataDeltaNode(key.segment(i), node);
 		}
 		node = new NoDataDeltaNode(name, node);
 		return assembleWith(node);
 	}

 	/**
 	 * Returns the child with the given local name.  The child must exist.
 	 */
 	AbstractDataTreeNode childAt(String localName) {
 		AbstractDataTreeNode node = childAtOrNull(localName);
 		if (node != null) {
 			return node;
 		}
 		throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
 	}

 	/**
 	 * Returns the child with the given local name.  Returns null if the child
 	 * does not exist.
 	 *
 	 * @param localName
 	 *	name of child to retrieve
 	 */
 	AbstractDataTreeNode childAtOrNull(String localName) {
 		int index = indexOfChild(localName);
 		return index >= 0 ? children[index] : null;
 	}

 	/**
 	 * Returns the child with the given local name, ignoring case.
 	 * If multiple case variants exist, the search will favour real nodes
 	 * over deleted nodes. If multiple real nodes are found, the first one
 	 * encountered in case order is returned. Returns null if no matching
 	 * children are found.
 	 *
 	 * @param localName name of child to retrieve
 	 */
 	AbstractDataTreeNode childAtIgnoreCase(String localName) {
 		AbstractDataTreeNode result = null;
 		for (AbstractDataTreeNode element : children) {
 			if (element.getName().equalsIgnoreCase(localName)) {
 				//if we find a deleted child, keep looking for a real child
 				if (element.isDeleted())
 					result = element;
 				else
 					return element;
 			}
 		}
 		return result;
 	}

 	/**
 	 */
 	protected static AbstractDataTreeNode[] compareWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparator) {

 		int oldLen = oldNodes.length;
 		int newLen = newNodes.length;
 		int oldIndex = 0;
 		int newIndex = 0;
 		AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[oldLen + newLen];
 		int count = 0;

 		while (oldIndex < oldLen && newIndex < newLen) {
 			DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex];
 			DataTreeNode newNode = (DataTreeNode) newNodes[newIndex];
 			int compare = oldNode.name.compareTo(newNode.name);
 			if (compare < 0) {
 				/* give the client a chance to say whether it should be in the delta */
 				int userComparison = comparator.compare(oldNode.getData(), null);
 				if (userComparison != 0) {
 					comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
 				}
 				++oldIndex;
 			} else if (compare > 0) {
 				/* give the client a chance to say whether it should be in the delta */
 				int userComparison = comparator.compare(null, newNode.getData());
 				if (userComparison != 0) {
 					comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
 				}
 				++newIndex;
 			} else {
 				AbstractDataTreeNode comparedNode = oldNode.compareWith(newNode, comparator);
 				NodeComparison comparison = (NodeComparison) comparedNode.getData();

 				/* skip empty comparisons */
 				if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
 					comparedNodes[count++] = comparedNode;
 				}
 				++oldIndex;
 				++newIndex;
 			}
 		}
 		while (oldIndex < oldLen) {
 			DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex++];

 			/* give the client a chance to say whether it should be in the delta */
 			int userComparison = comparator.compare(oldNode.getData(), null);
 			if (userComparison != 0) {
 				comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
 			}
 		}
 		while (newIndex < newLen) {
 			DataTreeNode newNode = (DataTreeNode) newNodes[newIndex++];

 			/* give the client a chance to say whether it should be in the delta */
 			int userComparison = comparator.compare(null, newNode.getData());
 			if (userComparison != 0) {
 				comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
 			}
 		}

 		if (count == 0) {
 			return NO_CHILDREN;
 		}
 		if (count < comparedNodes.length) {
 			System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
 		}
 		return comparedNodes;
 	}

 	/**
 	 */
 	protected static AbstractDataTreeNode[] compareWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparator) {

 		AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[nodes.length];
 		int count = 0;
 		for (AbstractDataTreeNode node : nodes) {
 			AbstractDataTreeNode comparedNode = node.compareWithParent(key.append(node.getName()), parent, comparator);
 			NodeComparison comparison = (NodeComparison) comparedNode.getData();
 			// Skip it if it's an empty comparison (and no children).
 			if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
 				comparedNodes[count++] = comparedNode;
 			}
 		}
 		if (count == 0) {
 			return NO_CHILDREN;
 		}
 		if (count < comparedNodes.length) {
 			System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
 		}
 		return comparedNodes;
 	}

 	abstract AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator);

 	static AbstractDataTreeNode convertToAddedComparisonNode(AbstractDataTreeNode newNode, int userComparison) {
 		AbstractDataTreeNode[] children = newNode.getChildren();
 		int n = children.length;
 		AbstractDataTreeNode[] convertedChildren;
 		if (n == 0) {
 			convertedChildren = NO_CHILDREN;
 		} else {
 			convertedChildren = new AbstractDataTreeNode[n];
 			for (int i = 0; i < n; ++i) {
 				convertedChildren[i] = convertToAddedComparisonNode(children[i], userComparison);
 			}
 		}
 		return new DataTreeNode(newNode.name, new NodeComparison(null, newNode.getData(), NodeComparison.K_ADDED, userComparison), convertedChildren);
 	}

 	static AbstractDataTreeNode convertToRemovedComparisonNode(AbstractDataTreeNode oldNode, int userComparison) {
 		AbstractDataTreeNode[] children = oldNode.getChildren();
 		int n = children.length;
 		AbstractDataTreeNode[] convertedChildren;
 		if (n == 0) {
 			convertedChildren = NO_CHILDREN;
 		} else {
 			convertedChildren = new AbstractDataTreeNode[n];
 			for (int i = 0; i < n; ++i) {
 				convertedChildren[i] = convertToRemovedComparisonNode(children[i], userComparison);
 			}
 		}
 		return new DataTreeNode(oldNode.name, new NodeComparison(oldNode.getData(), null, NodeComparison.K_REMOVED, userComparison), convertedChildren);
 	}

 	/**
 	 * Returns a copy of the receiver which shares the receiver elements
 	 */
 	abstract AbstractDataTreeNode copy();

 	/**
 	 * Replaces the receiver's children between "from" and "to", with the children
 	 * in otherNode starting at "start".  This method replaces the Smalltalk
 	 * #replaceFrom:to:with:startingAt: method for copying children in data nodes
 	 */
 	protected void copyChildren(int from, int to, AbstractDataTreeNode otherNode, int start) {
 		int other = start;
 		for (int i = from; i <= to; i++, other++) {
 			this.children[i] = otherNode.children[other];
 		}
 	}

 	/**
 	 * Returns an array of the node's children
 	 */
 	public AbstractDataTreeNode[] getChildren() {
 		return children;
 	}

 	/**
 	 * Returns the node's data
 	 */
 	Object getData() {
 		throw new AbstractMethodError(Messages.dtree_subclassImplement);
 	}

 	/**
 	 * return the name of the node
 	 */
 	public String getName() {
 		return name;
 	}

 	/**
 	 * Returns true if the receiver can carry data, false otherwise.
 	 */
 	boolean hasData() {
 		return false;
 	}

 	/**
 	 * Returns true if the receiver has a child with the given local name,
 	 * false otherwise
 	 */
 	boolean includesChild(String localName) {
 		return indexOfChild(localName) != -1;
 	}

 	/**
 	 * Returns the index of the specified child's name in the receiver.
 	 */
 	protected int indexOfChild(String localName) {
 		AbstractDataTreeNode[] nodes = this.children;
 		int left = 0;
 		int right = nodes.length - 1;
 		while (left <= right) {
 			int mid = (left + right) / 2;
 			int compare = localName.compareTo(nodes[mid].name);
 			if (compare < 0) {
 				right = mid - 1;
 			} else if (compare > 0) {
 				left = mid + 1;
 			} else {
 				return mid;
 			}
 		}
 		return -1;
 	}

 	/**
 	 * Returns true if the receiver represents a deleted node, false otherwise.
 	 */
 	boolean isDeleted() {
 		return false;
 	}

 	/**
 	 * Returns true if the receiver represents delta information,
 	 * false if it represents the complete information.
 	 */
 	boolean isDelta() {
 		return false;
 	}

 	/**
 	 * Returns true if the receiver is an empty delta node, false otherwise.
 	 */
 	boolean isEmptyDelta() {
 		return false;
 	}

 	/**
 	 * Returns the local names of the receiver's children.
 	 */
 	String[] namesOfChildren() {
 		String names[] = new String[children.length];
 		/* copy child names (Reverse loop optimized) */
 		for (int i = children.length; --i >= 0;)
 			names[i] = children[i].getName();
 		return names;
 	}

 	/**
 	 * Replaces the child with the given local name.
 	 */
 	void replaceChild(String localName, DataTreeNode node) {
 		int i = indexOfChild(localName);
 		if (i >= 0) {
 			children[i] = node;
 		} else {
 			throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
 		}
 	}

 	/**
 	 * Set the node's children
 	 */
 	protected void setChildren(AbstractDataTreeNode newChildren[]) {
 		children = newChildren;
 	}

 	/**
 	 * Set the node's name
 	 */
 	void setName(String s) {
 		name = s;
 	}

 	/**
 	 * Simplifies the given nodes, and answers their replacements.
 	 */
 	protected static AbstractDataTreeNode[] simplifyWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparer) {
 		int nodeCount = nodes.length;
 		if (nodeCount == 0)
 			return NO_CHILDREN;
 		AbstractDataTreeNode[] simplifiedNodes = new AbstractDataTreeNode[nodeCount];
 		int simplifiedCount = 0;
 		for (int i = 0; i < nodeCount; ++i) {
 			AbstractDataTreeNode node = nodes[i];
 			AbstractDataTreeNode simplifiedNode = node.simplifyWithParent(key.append(node.getName()), parent, comparer);
 			if (!simplifiedNode.isEmptyDelta()) {
 				simplifiedNodes[simplifiedCount++] = simplifiedNode;
 			}
 		}
 		if (simplifiedCount == 0) {
 			return NO_CHILDREN;
 		}
 		if (simplifiedCount < simplifiedNodes.length) {
 			System.arraycopy(simplifiedNodes, 0, simplifiedNodes = new AbstractDataTreeNode[simplifiedCount], 0, simplifiedCount);
 		}
 		return simplifiedNodes;
 	}

 	/**
 	 * Simplifies the given node, and answers its replacement.
 	 */
 	abstract AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer);

 	/**
 	 * Returns the number of children of the receiver
 	 */
 	int size() {
 		return children.length;
 	}

 	/* (non-Javadoc
 	 * Method declared on IStringPoolParticipant
 	 */
 	public void storeStrings(StringPool set) {
 		name = set.add(name);
 		//copy children pointer in case of concurrent modification
 		AbstractDataTreeNode[] nodes = children;
 		if (nodes != null)
 			for (int i = nodes.length; --i >= 0;)
 				nodes[i].storeStrings(set);
 	}

 	/**
 	 * Returns a unicode representation of the node.  This method is used
 	 * for debugging purposes only (no NLS support needed)
 	 */
 	@Override
 	public String toString() {
 		return "an AbstractDataTreeNode(" + this.getName() + ") with " + getChildren().length + " children."; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 	}

 	/**
 	 * Returns a constant describing the type of node.
 	 */
 	abstract int type();
 }
	/*******************************************************************************
	* Copyright (c) 2000, 2014 IBM Corporation and others.
	* All rights reserved. This program and the accompanying materials
	* are made available under the terms of the Eclipse Public License v1.0
	* which accompanies this distribution, and is available at
	* http://www.eclipse.org/legal/epl-v10.html
	*
	* Contributors:
	* IBM Corporation - initial API and implementation
	* Thomas Wolf (Paranor AG) -- optimize assembleWith
	*******************************************************************************/
	package org.eclipse.core.internal.dtree;

	import org.eclipse.core.internal.utils.Messages;
	import org.eclipse.core.internal.utils.StringPool;
	import org.eclipse.core.runtime.IPath;
	import org.eclipse.osgi.util.NLS;

	/**
	* This class and its subclasses are used to represent nodes of AbstractDataTrees.
	* Refer to the DataTree API comments for more details.
	* @see AbstractDataTree
	*/
	public abstract class AbstractDataTreeNode {
	/**
	* Singleton indicating no children.
	*/
	static final AbstractDataTreeNode[] NO_CHILDREN = new AbstractDataTreeNode[0];
	protected AbstractDataTreeNode children[];
	protected String name;

	/* Node types for comparison */
	public static final int T_COMPLETE_NODE = 0;
	public static final int T_DELTA_NODE = 1;
	public static final int T_DELETED_NODE = 2;
	public static final int T_NO_DATA_DELTA_NODE = 3;

	/**
	* Creates a new data tree node
	*
	* @param name
	* name of new node
	* @param children
	* children of the new node
	*/
	AbstractDataTreeNode(String name, AbstractDataTreeNode[] children) {
	this.name = name;
	if (children == null \|\| children.length == 0)
	this.children = AbstractDataTreeNode.NO_CHILDREN;
	else
	this.children = children;
	}

	/**
	* Returns a node which if applied to the receiver will produce
	* the corresponding node in the given parent tree.
	*
	* @param myTree tree to which the node belongs
	* @param parentTree parent tree on which to base backward delta
	* @param key key of node in its tree
	*/
	abstract AbstractDataTreeNode asBackwardDelta(DeltaDataTree myTree, DeltaDataTree parentTree, IPath key);

	/**
	* If this node is a node in a comparison tree, this method reverses
	* the comparison for this node and all children
	*/
	AbstractDataTreeNode asReverseComparisonNode(IComparator comparator) {
	return this;
	}

	/**
	* Returns the result of assembling nodes with the given forward delta nodes.
	* Both arrays must be sorted by name.
	* The result is sorted by name.
	* If keepDeleted is true, explicit representations of deletions are kept,
	* otherwise nodes to be deleted are removed in the result.
	*/
	static AbstractDataTreeNode[] assembleWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, boolean keepDeleted) {

	// Optimize the common case where the new list is empty.
	if (newNodes.length == 0)
	return oldNodes;

	// Can't just return newNodes if oldNodes has length 0
	// because newNodes may contain deleted nodes.

	AbstractDataTreeNode[] resultNodes = new AbstractDataTreeNode[oldNodes.length + newNodes.length];

	// do a merge
	int oldIndex = 0;
	int newIndex = 0;
	int resultIndex = 0;
	while (oldIndex < oldNodes.length && newIndex < newNodes.length) {
	int log2 = 31 - Integer.numberOfLeadingZeros(oldNodes.length - oldIndex);
	if (log2 > 1 && (newNodes.length - newIndex) <= (oldNodes.length - oldIndex) / log2) {
	// We can expect to fare better using binary search. In particular, this will optimize the case of a folder refresh (new linked
	// folder with many files in a flat hierarchy), where this is called repeatedly, with oldNodes containing the files added so far,
	// and newNodes containing exactly one new node for the next file to be added. The old algorithm has quadratic performance
	// (O((n+1)n/2); number of string comparisons is the dominating component here) in this case; this new algorithm does O(nlog(n))
	// string comparisons.
	String key = newNodes[newIndex].name;
	// Figure out where to insert the next new node.
	int left = oldIndex;
	int right = oldNodes.length - 1;
	boolean found = false;
	while (left <= right) {
	int mid = (left + right) / 2;
	int compare = key.compareTo(oldNodes[mid].name);
	if (compare < 0) {
	right = mid - 1;
	} else if (compare > 0) {
	left = mid + 1;
	} else {
	left = mid;
	found = true;
	break;
	}
	}
	// Now copy oldNodes from oldIndex to left-1, insert the new node, increment newIndex
	int toCopy = left - oldIndex;
	System.arraycopy(oldNodes, oldIndex, resultNodes, resultIndex, toCopy);
	resultIndex += toCopy;
	if (found) {
	AbstractDataTreeNode node = oldNodes[left++].assembleWith(newNodes[newIndex++]);
	if (node != null && (!node.isDeleted() \|\| keepDeleted)) {
	resultNodes[resultIndex++] = node;
	}
	} else {
	AbstractDataTreeNode node = newNodes[newIndex++];
	if (!node.isDeleted() \|\| keepDeleted) {
	resultNodes[resultIndex++] = node;
	}
	}
	oldIndex = left;
	} else {
	int compare = oldNodes[oldIndex].name.compareTo(newNodes[newIndex].name);
	if (compare == 0) {
	AbstractDataTreeNode node = oldNodes[oldIndex++].assembleWith(newNodes[newIndex++]);
	if (node != null && (!node.isDeleted() \|\| keepDeleted)) {
	resultNodes[resultIndex++] = node;
	}
	} else if (compare < 0) {
	resultNodes[resultIndex++] = oldNodes[oldIndex++];
	} else if (compare > 0) {
	AbstractDataTreeNode node = newNodes[newIndex++];
	if (!node.isDeleted() \|\| keepDeleted) {
	resultNodes[resultIndex++] = node;
	}
	}
	}
	}
	while (oldIndex < oldNodes.length) {
	resultNodes[resultIndex++] = oldNodes[oldIndex++];
	}
	while (newIndex < newNodes.length) {
	AbstractDataTreeNode resultNode = newNodes[newIndex++];
	if (!resultNode.isDeleted() \|\| keepDeleted) {
	resultNodes[resultIndex++] = resultNode;
	}
	}

	// trim size of result
	if (resultIndex < resultNodes.length) {
	System.arraycopy(resultNodes, 0, resultNodes = new AbstractDataTreeNode[resultIndex], 0, resultIndex);
	}
	return resultNodes;
	}

	/**
	* Returns the result of assembling this node with the given forward delta node.
	*/
	AbstractDataTreeNode assembleWith(AbstractDataTreeNode node) {

	// If not a delta, or if the old node was deleted,
	// then the new node represents the complete picture.
	if (!node.isDelta() \|\| this.isDeleted()) {
	return node;
	}

	// node must be either a DataDeltaNode or a NoDataDeltaNode
	if (node.hasData()) {
	if (this.isDelta()) {
	// keep deletions because they still need
	// to hide child nodes in the parent.
	AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
	return new DataDeltaNode(name, node.getData(), assembledChildren);
	}
	// This is a complete picture, so deletions
	// wipe out the child and are no longer useful
	AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
	return new DataTreeNode(name, node.getData(), assembledChildren);
	}
	if (this.isDelta()) {
	AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, true);
	if (this.hasData())
	return new DataDeltaNode(name, this.getData(), assembledChildren);
	return new NoDataDeltaNode(name, assembledChildren);
	}
	AbstractDataTreeNode[] assembledChildren = assembleWith(children, node.children, false);
	return new DataTreeNode(name, this.getData(), assembledChildren);
	}

	/**
	* Returns the result of assembling this node with the given forward delta node.
	*/
	AbstractDataTreeNode assembleWith(AbstractDataTreeNode node, IPath key, int keyIndex) {

	// leaf case
	int keyLen = key.segmentCount();
	if (keyIndex == keyLen) {
	return assembleWith(node);
	}

	// non-leaf case
	int childIndex = indexOfChild(key.segment(keyIndex));
	if (childIndex >= 0) {
	AbstractDataTreeNode copy = copy();
	copy.children[childIndex] = children[childIndex].assembleWith(node, key, keyIndex + 1);
	return copy;
	}

	// Child not found. Build up NoDataDeltaNode hierarchy for rest of key
	// and assemble with that.
	for (int i = keyLen - 2; i >= keyIndex; --i) {
	node = new NoDataDeltaNode(key.segment(i), node);
	}
	node = new NoDataDeltaNode(name, node);
	return assembleWith(node);
	}

	/**
	* Returns the child with the given local name. The child must exist.
	*/
	AbstractDataTreeNode childAt(String localName) {
	AbstractDataTreeNode node = childAtOrNull(localName);
	if (node != null) {
	return node;
	}
	throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
	}

	/**
	* Returns the child with the given local name. Returns null if the child
	* does not exist.
	*
	* @param localName
	* name of child to retrieve
	*/
	AbstractDataTreeNode childAtOrNull(String localName) {
	int index = indexOfChild(localName);
	return index >= 0 ? children[index] : null;
	}

	/**
	* Returns the child with the given local name, ignoring case.
	* If multiple case variants exist, the search will favour real nodes
	* over deleted nodes. If multiple real nodes are found, the first one
	* encountered in case order is returned. Returns null if no matching
	* children are found.
	*
	* @param localName name of child to retrieve
	*/
	AbstractDataTreeNode childAtIgnoreCase(String localName) {
	AbstractDataTreeNode result = null;
	for (AbstractDataTreeNode element : children) {
	if (element.getName().equalsIgnoreCase(localName)) {
	//if we find a deleted child, keep looking for a real child
	if (element.isDeleted())
	result = element;
	else
	return element;
	}
	}
	return result;
	}

	/**
	*/
	protected static AbstractDataTreeNode[] compareWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, IComparator comparator) {

	int oldLen = oldNodes.length;
	int newLen = newNodes.length;
	int oldIndex = 0;
	int newIndex = 0;
	AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[oldLen + newLen];
	int count = 0;

	while (oldIndex < oldLen && newIndex < newLen) {
	DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex];
	DataTreeNode newNode = (DataTreeNode) newNodes[newIndex];
	int compare = oldNode.name.compareTo(newNode.name);
	if (compare < 0) {
	/* give the client a chance to say whether it should be in the delta */
	int userComparison = comparator.compare(oldNode.getData(), null);
	if (userComparison != 0) {
	comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
	}
	++oldIndex;
	} else if (compare > 0) {
	/* give the client a chance to say whether it should be in the delta */
	int userComparison = comparator.compare(null, newNode.getData());
	if (userComparison != 0) {
	comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
	}
	++newIndex;
	} else {
	AbstractDataTreeNode comparedNode = oldNode.compareWith(newNode, comparator);
	NodeComparison comparison = (NodeComparison) comparedNode.getData();

	/* skip empty comparisons */
	if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
	comparedNodes[count++] = comparedNode;
	}
	++oldIndex;
	++newIndex;
	}
	}
	while (oldIndex < oldLen) {
	DataTreeNode oldNode = (DataTreeNode) oldNodes[oldIndex++];

	/* give the client a chance to say whether it should be in the delta */
	int userComparison = comparator.compare(oldNode.getData(), null);
	if (userComparison != 0) {
	comparedNodes[count++] = convertToRemovedComparisonNode(oldNode, userComparison);
	}
	}
	while (newIndex < newLen) {
	DataTreeNode newNode = (DataTreeNode) newNodes[newIndex++];

	/* give the client a chance to say whether it should be in the delta */
	int userComparison = comparator.compare(null, newNode.getData());
	if (userComparison != 0) {
	comparedNodes[count++] = convertToAddedComparisonNode(newNode, userComparison);
	}
	}

	if (count == 0) {
	return NO_CHILDREN;
	}
	if (count < comparedNodes.length) {
	System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
	}
	return comparedNodes;
	}

	/**
	*/
	protected static AbstractDataTreeNode[] compareWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparator) {

	AbstractDataTreeNode[] comparedNodes = new AbstractDataTreeNode[nodes.length];
	int count = 0;
	for (AbstractDataTreeNode node : nodes) {
	AbstractDataTreeNode comparedNode = node.compareWithParent(key.append(node.getName()), parent, comparator);
	NodeComparison comparison = (NodeComparison) comparedNode.getData();
	// Skip it if it's an empty comparison (and no children).
	if (!(comparison.isUnchanged() && comparedNode.size() == 0)) {
	comparedNodes[count++] = comparedNode;
	}
	}
	if (count == 0) {
	return NO_CHILDREN;
	}
	if (count < comparedNodes.length) {
	System.arraycopy(comparedNodes, 0, comparedNodes = new AbstractDataTreeNode[count], 0, count);
	}
	return comparedNodes;
	}

	abstract AbstractDataTreeNode compareWithParent(IPath key, DeltaDataTree parent, IComparator comparator);

	static AbstractDataTreeNode convertToAddedComparisonNode(AbstractDataTreeNode newNode, int userComparison) {
	AbstractDataTreeNode[] children = newNode.getChildren();
	int n = children.length;
	AbstractDataTreeNode[] convertedChildren;
	if (n == 0) {
	convertedChildren = NO_CHILDREN;
	} else {
	convertedChildren = new AbstractDataTreeNode[n];
	for (int i = 0; i < n; ++i) {
	convertedChildren[i] = convertToAddedComparisonNode(children[i], userComparison);
	}
	}
	return new DataTreeNode(newNode.name, new NodeComparison(null, newNode.getData(), NodeComparison.K_ADDED, userComparison), convertedChildren);
	}

	static AbstractDataTreeNode convertToRemovedComparisonNode(AbstractDataTreeNode oldNode, int userComparison) {
	AbstractDataTreeNode[] children = oldNode.getChildren();
	int n = children.length;
	AbstractDataTreeNode[] convertedChildren;
	if (n == 0) {
	convertedChildren = NO_CHILDREN;
	} else {
	convertedChildren = new AbstractDataTreeNode[n];
	for (int i = 0; i < n; ++i) {
	convertedChildren[i] = convertToRemovedComparisonNode(children[i], userComparison);
	}
	}
	return new DataTreeNode(oldNode.name, new NodeComparison(oldNode.getData(), null, NodeComparison.K_REMOVED, userComparison), convertedChildren);
	}

	/**
	* Returns a copy of the receiver which shares the receiver elements
	*/
	abstract AbstractDataTreeNode copy();

	/**
	* Replaces the receiver's children between "from" and "to", with the children
	* in otherNode starting at "start". This method replaces the Smalltalk
	* #replaceFrom:to:with:startingAt: method for copying children in data nodes
	*/
	protected void copyChildren(int from, int to, AbstractDataTreeNode otherNode, int start) {
	int other = start;
	for (int i = from; i <= to; i++, other++) {
	this.children[i] = otherNode.children[other];
	}
	}

	/**
	* Returns an array of the node's children
	*/
	public AbstractDataTreeNode[] getChildren() {
	return children;
	}

	/**
	* Returns the node's data
	*/
	Object getData() {
	throw new AbstractMethodError(Messages.dtree_subclassImplement);
	}

	/**
	* return the name of the node
	*/
	public String getName() {
	return name;
	}

	/**
	* Returns true if the receiver can carry data, false otherwise.
	*/
	boolean hasData() {
	return false;
	}

	/**
	* Returns true if the receiver has a child with the given local name,
	* false otherwise
	*/
	boolean includesChild(String localName) {
	return indexOfChild(localName) != -1;
	}

	/**
	* Returns the index of the specified child's name in the receiver.
	*/
	protected int indexOfChild(String localName) {
	AbstractDataTreeNode[] nodes = this.children;
	int left = 0;
	int right = nodes.length - 1;
	while (left <= right) {
	int mid = (left + right) / 2;
	int compare = localName.compareTo(nodes[mid].name);
	if (compare < 0) {
	right = mid - 1;
	} else if (compare > 0) {
	left = mid + 1;
	} else {
	return mid;
	}
	}
	return -1;
	}

	/**
	* Returns true if the receiver represents a deleted node, false otherwise.
	*/
	boolean isDeleted() {
	return false;
	}

	/**
	* Returns true if the receiver represents delta information,
	* false if it represents the complete information.
	*/
	boolean isDelta() {
	return false;
	}

	/**
	* Returns true if the receiver is an empty delta node, false otherwise.
	*/
	boolean isEmptyDelta() {
	return false;
	}

	/**
	* Returns the local names of the receiver's children.
	*/
	String[] namesOfChildren() {
	String names[] = new String[children.length];
	/* copy child names (Reverse loop optimized) */
	for (int i = children.length; --i >= 0;)
	names[i] = children[i].getName();
	return names;
	}

	/**
	* Replaces the child with the given local name.
	*/
	void replaceChild(String localName, DataTreeNode node) {
	int i = indexOfChild(localName);
	if (i >= 0) {
	children[i] = node;
	} else {
	throw new ObjectNotFoundException(NLS.bind(Messages.dtree_missingChild, localName));
	}
	}

	/**
	* Set the node's children
	*/
	protected void setChildren(AbstractDataTreeNode newChildren[]) {
	children = newChildren;
	}

	/**
	* Set the node's name
	*/
	void setName(String s) {
	name = s;
	}

	/**
	* Simplifies the given nodes, and answers their replacements.
	*/
	protected static AbstractDataTreeNode[] simplifyWithParent(AbstractDataTreeNode[] nodes, IPath key, DeltaDataTree parent, IComparator comparer) {
	int nodeCount = nodes.length;
	if (nodeCount == 0)
	return NO_CHILDREN;
	AbstractDataTreeNode[] simplifiedNodes = new AbstractDataTreeNode[nodeCount];
	int simplifiedCount = 0;
	for (int i = 0; i < nodeCount; ++i) {
	AbstractDataTreeNode node = nodes[i];
	AbstractDataTreeNode simplifiedNode = node.simplifyWithParent(key.append(node.getName()), parent, comparer);
	if (!simplifiedNode.isEmptyDelta()) {
	simplifiedNodes[simplifiedCount++] = simplifiedNode;
	}
	}
	if (simplifiedCount == 0) {
	return NO_CHILDREN;
	}
	if (simplifiedCount < simplifiedNodes.length) {
	System.arraycopy(simplifiedNodes, 0, simplifiedNodes = new AbstractDataTreeNode[simplifiedCount], 0, simplifiedCount);
	}
	return simplifiedNodes;
	}

	/**
	* Simplifies the given node, and answers its replacement.
	*/
	abstract AbstractDataTreeNode simplifyWithParent(IPath key, DeltaDataTree parent, IComparator comparer);

	/**
	* Returns the number of children of the receiver
	*/
	int size() {
	return children.length;
	}

	/* (non-Javadoc
	* Method declared on IStringPoolParticipant
	*/
	public void storeStrings(StringPool set) {
	name = set.add(name);
	//copy children pointer in case of concurrent modification
	AbstractDataTreeNode[] nodes = children;
	if (nodes != null)
	for (int i = nodes.length; --i >= 0;)
	nodes[i].storeStrings(set);
	}

	/**
	* Returns a unicode representation of the node. This method is used
	* for debugging purposes only (no NLS support needed)
	*/
	@Override
	public String toString() {
	return "an AbstractDataTreeNode(" + this.getName() + ") with " + getChildren().length + " children."; //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
	}

	/**
	* Returns a constant describing the type of node.
	*/
	abstract int type();
	}