Copyright (c) 2000, 2014 IBM Corporation and others.
This program and the accompanying materials
are made available under the terms of the Eclipse Public License 2.0
which accompanies this distribution, and is available at
https://www.eclipse.org/legal/epl-2.0/
SPDX-License-Identifier: EPL-2.0
Contributors:
    IBM Corporation - initial API and implementation
    Thomas Wolf (Paranor AG) -- optimize assembleWith
/*******************************************************************************
 * Copyright (c) 2000, 2014 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * 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 Also:
AbstractDataTree/**
 * 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.
/**
	 * 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
Params:
name – 
name of new node
children – 
children of the new node/**
	 * 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.
Params:
myTree –  tree to which the node belongs
parentTree –  parent tree on which to base backward delta
key –  key of node in its tree/**
	 * 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
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
Params:
localName – 
name of child to retrieve/**
	 * 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.
Params:
localName – name of child to retrieve/**
	 * 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
/**
	 * 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
/**
	 * 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
/**
	 * Returns an array of the node's children
	 */
	public AbstractDataTreeNode[] getChildren() {
		return children;
	}

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

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

	
Returns true if the receiver can carry data, false otherwise.
/**
	 * 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
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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
/**
	 * Set the node's children
	 */
	protected void setChildren(AbstractDataTreeNode newChildren[]) {
		children = newChildren;
	}

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

	
Simplifies the given nodes, and answers their replacements.
/**
	 * 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.
/**
	 * 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
/**
	 * 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)
/**
	 * 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.
/**
	 * Returns a constant describing the type of node.
	 */
	abstract int type();
}