org.eclipse.platform/org.eclipse.core.resources/3.13.600 : org/eclipse/core/internal/dtree/DeltaDataTree.java

DeltaDataTree
http://www.eclipse.org/platform: Core Resource Management (Eclipse Foundation)
Eclipse Public License - v 2.0
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
/*******************************************************************************
 * 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
 *******************************************************************************/
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.*;

Externally, a DeltaDataTree appears to have the same content as
a standard data tree.  Internally, the delta tree may be complete, or it may
just indicate the changes between itself and its parent.
Nodes that exist in the parent but do not exist in the delta, are represented
as instances of DeletedNode.  Nodes that are identical in the parent
and the delta, but have differences in their subtrees, are represented as
instances of NoDataDeltaNode in the delta tree.  Nodes that differ
between parent and delta are instances of DataDeltaNode.  However,
the DataDeltaNode only contains the children whose subtrees differ
between parent and delta.
A delta tree algebra is used to manipulate sets of delta trees.  Given two trees,
one can obtain the delta between the two using the method
forwardDeltaWith(aTree).  Given a tree and a delta, one can assemble
the complete tree that the delta represents using the method 
assembleWithForwardDelta.  Refer to the public API methods of this class
for further details.
/**
 * Externally, a <code>DeltaDataTree</code> appears to have the same content as
 * a standard data tree.  Internally, the delta tree may be complete, or it may
 * just indicate the changes between itself and its parent.
 *
 * <p>Nodes that exist in the parent but do not exist in the delta, are represented
 * as instances of <code>DeletedNode</code>.  Nodes that are identical in the parent
 * and the delta, but have differences in their subtrees, are represented as
 * instances of <code>NoDataDeltaNode</code> in the delta tree.  Nodes that differ
 * between parent and delta are instances of <code>DataDeltaNode</code>.  However,
 * the <code>DataDeltaNode</code> only contains the children whose subtrees differ
 * between parent and delta.
 *
 * A delta tree algebra is used to manipulate sets of delta trees.  Given two trees,
 * one can obtain the delta between the two using the method
 * <code>forwardDeltaWith(aTree)</code>.  Given a tree and a delta, one can assemble
 * the complete tree that the delta represents using the method <code>
 * assembleWithForwardDelta</code>.  Refer to the public API methods of this class
 * for further details.
 */

public class DeltaDataTree extends AbstractDataTree {
	private AbstractDataTreeNode rootNode;
	private DeltaDataTree parent;

	Creates a new empty tree.
/**
	 * Creates a new empty tree.
	 */
	public DeltaDataTree() {
		this.empty();
	}

	Creates a new tree.
Params: rootNode – 
root node of new tree./**
	 * Creates a new tree.
	 * @param rootNode
	 *	root node of new tree.
	 */
	public DeltaDataTree(AbstractDataTreeNode rootNode) {
		this.rootNode = rootNode;
		this.parent = null;
	}

	protected DeltaDataTree(AbstractDataTreeNode rootNode, DeltaDataTree parent) {
		this.rootNode = rootNode;
		this.parent = parent;
	}

	Adds a child to the tree.
Params: parentKey – parent for new child.
localName – name of child.
childNode – child node./**
	 * Adds a child to the tree.
	 *
	 * @param parentKey parent for new child.
	 * @param localName name of child.
	 * @param childNode child node.
	 */
	protected void addChild(IPath parentKey, String localName, AbstractDataTreeNode childNode) {
		if (!includes(parentKey))
			handleNotFound(parentKey);
		childNode.setName(localName);
		this.assembleNode(parentKey, new NoDataDeltaNode(parentKey.lastSegment(), childNode));
	}

	Returns the tree as a backward delta.  If the delta is applied to the tree it
will produce its parent. The receiver must have a forward
delta representation. I.e.:  Call the receiver's parent A,
and the receiver B.  The receiver's representation is A->B.
Returns the delta A<-B.  The result is equivalent to A, but has B as its parent.
/**
	 * Returns the tree as a backward delta.  If the delta is applied to the tree it
	 * will produce its parent. The receiver must have a forward
	 * delta representation. I.e.:  Call the receiver's parent A,
	 * and the receiver B.  The receiver's representation is A-&gt;B.
	 * Returns the delta A&lt;-B.  The result is equivalent to A, but has B as its parent.
	 */
	DeltaDataTree asBackwardDelta() {
		if (getParent() == null)
			return newEmptyDeltaTree();
		return new DeltaDataTree(getRootNode().asBackwardDelta(this, getParent(), rootKey()), this);
	}

	This method can only be called on a comparison tree created
using DeltaDataTree.compareWith().  This method flips the orientation
of the given comparison tree, so that additions become removals,
and vice-versa.  This method destructively changes the tree
as opposed to making a copy.
/**
	 * This method can only be called on a comparison tree created
	 * using DeltaDataTree.compareWith().  This method flips the orientation
	 * of the given comparison tree, so that additions become removals,
	 * and vice-versa.  This method destructively changes the tree
	 * as opposed to making a copy.
	 */
	public DeltaDataTree asReverseComparisonTree(IComparator comparator) {
		/* don't reverse the root node if it's the absolute root (name==null) */
		if (rootNode.getName() == null) {
			AbstractDataTreeNode[] children = rootNode.getChildren();
			int nextChild = 0;
			for (AbstractDataTreeNode c : children) {
				AbstractDataTreeNode newChild = c.asReverseComparisonNode(comparator);
				if (newChild != null) {
					children[nextChild++] = newChild;
				}
			}

			if (nextChild < children.length) {
				AbstractDataTreeNode[] newChildren = new AbstractDataTreeNode[nextChild];
				System.arraycopy(children, 0, newChildren, 0, nextChild);
				rootNode.setChildren(newChildren);
			}
		} else {
			rootNode.asReverseComparisonNode(comparator);
		}
		return this;
	}

	Replaces a node in the tree with the result of assembling the node
with the given delta node (which represents a forward delta on
the existing node).
Params: key – key of the node to replace.
deltaNode – delta node to use to assemble the new node./**
	 * Replaces a node in the tree with the result of assembling the node
	 * with the given delta node (which represents a forward delta on
	 * the existing node).
	 *
	 * @param key key of the node to replace.
	 * @param deltaNode delta node to use to assemble the new node.
	 */
	protected void assembleNode(IPath key, AbstractDataTreeNode deltaNode) {
		rootNode = rootNode.assembleWith(deltaNode, key, 0);
	}

	Assembles the receiver with the given delta tree and answer
the resulting, mutable source tree.  The given delta tree must be a
forward delta based on the receiver (i.e. missing information is taken from
the receiver).  This operation is used to coalesce delta trees.
In detail, suppose that c is a forward delta over source tree a.
Let d := a assembleWithForwardDelta: c.
d has the same content as c, and is represented as a delta tree
whose parent is the same as a's parent.
In general, if c is represented as a chain of deltas of length n,
then d is represented as a chain of length n-1.
So if a is a complete tree (i.e., has no parent, length=0), then d
will be a complete tree too.
Corollary: (a assembleWithForwardDelta: (a forwardDeltaWith: b)) = b
/**
	 * Assembles the receiver with the given delta tree and answer
	 * the resulting, mutable source tree.  The given delta tree must be a
	 * forward delta based on the receiver (i.e. missing information is taken from
	 * the receiver).  This operation is used to coalesce delta trees.
	 *
	 * <p>In detail, suppose that c is a forward delta over source tree a.
	 * Let d := a assembleWithForwardDelta: c.
	 * d has the same content as c, and is represented as a delta tree
	 * whose parent is the same as a's parent.
	 *
	 * <p>In general, if c is represented as a chain of deltas of length n,
	 * then d is represented as a chain of length n-1.
	 *
	 * <p>So if a is a complete tree (i.e., has no parent, length=0), then d
	 * will be a complete tree too.
	 *
	 * <p>Corollary: (a assembleWithForwardDelta: (a forwardDeltaWith: b)) = b
	 */
	public DeltaDataTree assembleWithForwardDelta(DeltaDataTree deltaTree) {
		return new DeltaDataTree(getRootNode().assembleWith(deltaTree.getRootNode()), this);
	}

	Compares this tree with another tree, starting from the given path.  The
given path will be the root node of the returned tree.  Both this
tree and other tree must contain the given path.
/**
	 * Compares this tree with another tree, starting from the given path.  The
	 * given path will be the root node of the returned tree.  Both this
	 * tree and other tree must contain the given path.
	 */
	protected DeltaDataTree basicCompare(DeltaDataTree other, IComparator comparator, IPath path) {
		DeltaDataTree newTree;
		if (this == other) {
			newTree = new DeltaDataTree();
			newTree.setData(Path.ROOT, new NodeComparison(null, null, 0, 0));
		} else if (other.hasAncestor(this)) {
			AbstractDataTreeNode assembled = other.searchNodeAt(path);
			DeltaDataTree tree = other;

			/* Iterate through the receiver's ancestors until the receiver is reached */
			while ((tree = tree.getParent()) != this) {
				//ancestor may not contain the given path
				AbstractDataTreeNode treeNode = tree.searchNodeAt(path);
				if (treeNode != null) {
					assembled = treeNode.assembleWith(assembled);
				}
			}
			AbstractDataTreeNode comparedRoot = assembled.compareWithParent(path, this, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		} else if (this.hasAncestor(other)) {
			AbstractDataTreeNode assembled = this.asBackwardDelta().searchNodeAt(path);
			DeltaDataTree tree = this;

			/* Iterate through the receiver's ancestors until the other tree is reached */
			while ((tree = tree.getParent()) != other) {
				assembled = assembled.assembleWith(tree.asBackwardDelta().searchNodeAt(path));
			}
			AbstractDataTreeNode comparedRoot = assembled.compareWithParent(path, this, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		} else {
			//revert to naive comparison
			DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(path);
			DataTreeNode otherCompleteRoot = (DataTreeNode) other.copyCompleteSubtree(path);
			AbstractDataTreeNode comparedRoot = thisCompleteRoot.compareWith(otherCompleteRoot, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		}
		newTree.immutable();
		return newTree;
	}

	Collapses this tree so that the given ancestor becomes its
immediate parent.  Afterwards, this tree will still have exactly the
same contents, but its internal structure will be compressed.
 This operation should be used to collapse chains of
delta trees that don't contain interesting intermediate states.
This is a destructive operation, since it modifies the structure of this
tree instance.  This tree must be immutable at the start of this operation,
and will be immutable afterwards.
Returns: this tree./**
	 * Collapses this tree so that the given ancestor becomes its
	 * immediate parent.  Afterwards, this tree will still have exactly the
	 * same contents, but its internal structure will be compressed.
	 *
	 * <p> This operation should be used to collapse chains of
	 * delta trees that don't contain interesting intermediate states.
	 *
	 * <p>This is a destructive operation, since it modifies the structure of this
	 * tree instance.  This tree must be immutable at the start of this operation,
	 * and will be immutable afterwards.
	 * @return this tree.
	 */
	public DeltaDataTree collapseTo(DeltaDataTree collapseTo, IComparator comparator) {
		if (this == collapseTo || getParent() == collapseTo) {
			//already collapsed
			return this;
		}
		//collapse my tree to be a forward delta of the parent's tree.
		//c will have the same content as this tree, but its parent will be "parent".
		DeltaDataTree c = collapseTo.forwardDeltaWith(this, comparator);

		//update my internal root node and parent pointers.
		this.parent = collapseTo;
		this.rootNode = c.rootNode;
		return this;
	}

	Returns a DeltaDataTree that describes the differences between
this tree and "other" tree.  Each node of the returned tree
will contain a NodeComparison object that describes the differences
between the two trees.
/**
	 * Returns a DeltaDataTree that describes the differences between
	 * this tree and "other" tree.  Each node of the returned tree
	 * will contain a NodeComparison object that describes the differences
	 * between the two trees.
	 */
	public DeltaDataTree compareWith(DeltaDataTree other, IComparator comparator) {

		DeltaDataTree newTree;
		if (this == other) {
			newTree = new DeltaDataTree();
			newTree.setData(Path.ROOT, new NodeComparison(null, null, 0, 0));
		} else if (other.hasAncestor(this)) {

			AbstractDataTreeNode assembled = other.getRootNode();
			DeltaDataTree tree = other;

			/* Iterate through the receiver's ancestors until the receiver is reached */
			while ((tree = tree.getParent()) != this) {
				assembled = tree.getRootNode().assembleWith(assembled);
			}
			AbstractDataTreeNode comparedRoot = assembled.compareWithParent(rootKey(), this, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		} else if (this.hasAncestor(other)) {
			AbstractDataTreeNode assembled = this.asBackwardDelta().getRootNode();
			DeltaDataTree tree = this;

			/* Iterate through the receiver's ancestors until the other tree is reached */
			while ((tree = tree.getParent()) != other) {
				assembled = assembled.assembleWith(tree.asBackwardDelta().getRootNode());
			}
			AbstractDataTreeNode comparedRoot = assembled.compareWithParent(rootKey(), this, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		} else {
			//revert to naive comparison if trees have no common ancestry
			DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(rootKey());
			DataTreeNode otherCompleteRoot = (DataTreeNode) other.copyCompleteSubtree(rootKey());
			AbstractDataTreeNode comparedRoot = thisCompleteRoot.compareWith(otherCompleteRoot, comparator);
			newTree = new DeltaDataTree(comparedRoot);
		}
		newTree.immutable();
		return newTree;
	}

	Compares this tree with another tree, starting from the given path.  The
given path will be the root node of the returned tree.
/**
	 * Compares this tree with another tree, starting from the given path.  The
	 * given path will be the root node of the returned tree.
	 */
	public DeltaDataTree compareWith(DeltaDataTree other, IComparator comparator, IPath path) {
		/* need to figure out if trees really contain the given path */
		if (this.includes(path)) {
			if (other.includes(path))
				return basicCompare(other, comparator, path);
			/* only exists in this tree */
			return new DeltaDataTree(AbstractDataTreeNode.convertToRemovedComparisonNode(this.copyCompleteSubtree(path), comparator.compare(this.getData(path), null)));
		}
		if (other.includes(path))
			/* only exists in other tree */
			return new DeltaDataTree(AbstractDataTreeNode.convertToAddedComparisonNode(other.copyCompleteSubtree(path), comparator.compare(null, other.getData(path))));
		/* doesn't exist in either tree */
		return DeltaDataTree.createEmptyDelta();
	}

	Returns a copy of the tree which shares its instance variables.
/**
	 * Returns a copy of the tree which shares its instance variables.
	 */
	@Override
	protected AbstractDataTree copy() {
		return new DeltaDataTree(rootNode, parent);
	}

	Returns a complete node containing the contents of a subtree of the tree.
Params: key – 
key of subtree to copy/**
	 * Returns a complete node containing the contents of a subtree of the tree.
	 *
	 * @param key
	 *	key of subtree to copy
	 */
	@Override
	public AbstractDataTreeNode copyCompleteSubtree(IPath key) {
		AbstractDataTreeNode node = searchNodeAt(key);
		if (node == null) {
			handleNotFound(key);
			return null;
		}
		if (node.isDelta())
			return naiveCopyCompleteSubtree(key);
		//copy the node in case the user wants to hammer the subtree name
		return node.copy();
	}

	See Also: createChild.createChild(IPath, String)/**
	 * @see AbstractDataTree#createChild(IPath, String)
	 */
	@Override
	public void createChild(IPath parentKey, String localName) {
		createChild(parentKey, localName, null);
	}

	See Also: createChild.createChild(IPath, String, Object)/**
	 * @see AbstractDataTree#createChild(IPath, String, Object)
	 */
	@Override
	public void createChild(IPath parentKey, String localName, Object data) {
		if (isImmutable())
			handleImmutableTree();
		addChild(parentKey, localName, new DataTreeNode(localName, data));
	}

	Returns a delta data tree that represents an empty delta.
(i.e. it represents a delta on another (unspecified) tree,
but introduces no changes).
/**
	 * Returns a delta data tree that represents an empty delta.
	 * (i.e. it represents a delta on another (unspecified) tree,
	 * but introduces no changes).
	 */
	static DeltaDataTree createEmptyDelta() {

		DeltaDataTree newTree = new DeltaDataTree();
		newTree.emptyDelta();
		return newTree;
	}

	Creates and returns an instance of the receiver.
See Also: createInstance.createInstance()/**
	 * Creates and returns an instance of the receiver.
	 * @see AbstractDataTree#createInstance()
	 */
	@Override
	protected AbstractDataTree createInstance() {
		return new DeltaDataTree();
	}

	See Also: createSubtree.createSubtree(IPath, AbstractDataTreeNode)/**
	 * @see AbstractDataTree#createSubtree(IPath, AbstractDataTreeNode)
	 */
	@Override
	public void createSubtree(IPath key, AbstractDataTreeNode node) {
		if (isImmutable())
			handleImmutableTree();
		if (key.isRoot()) {
			setParent(null);
			setRootNode(node);
		} else {
			addChild(key.removeLastSegments(1), key.lastSegment(), node);
		}
	}

	See Also: deleteChild.deleteChild(IPath, String)/**
	 * @see AbstractDataTree#deleteChild(IPath, String)
	 */
	@Override
	public void deleteChild(IPath parentKey, String localName) {
		if (isImmutable())
			handleImmutableTree();
		/* If the child does not exist */
		IPath childKey = parentKey.append(localName);
		if (!includes(childKey))
			handleNotFound(childKey);
		assembleNode(parentKey, new NoDataDeltaNode(parentKey.lastSegment(), new DeletedNode(localName)));
	}

	Initializes the receiver so that it is a complete, empty tree.
See Also: empty.empty()/**
	 * Initializes the receiver so that it is a complete, empty tree.
	 * @see AbstractDataTree#empty()
	 */
	@Override
	public void empty() {
		rootNode = new DataTreeNode(null, null);
		parent = null;
	}

	Initializes the receiver so that it represents an empty delta.
(i.e. it represents a delta on another (unspecified) tree,
it introduces no changes).  The parent is left unchanged.
/**
	 * Initializes the receiver so that it represents an empty delta.
	 * (i.e. it represents a delta on another (unspecified) tree,
	 * it introduces no changes).  The parent is left unchanged.
	 */
	void emptyDelta() {
		rootNode = new NoDataDeltaNode(null);
	}

	Returns a node of the tree if it is present, otherwise returns null
Params: key – 
key of node to find/**
	 * Returns a node of the tree if it is present, otherwise returns null
	 *
	 * @param key
	 *	key of node to find
	 */
	public AbstractDataTreeNode findNodeAt(IPath key) {
		AbstractDataTreeNode node = rootNode;
		int segmentCount = key.segmentCount();
		for (int i = 0; i < segmentCount; i++) {
			node = node.childAtOrNull(key.segment(i));
			if (node == null)
				return null;
		}
		return node;
	}

	Returns a forward delta between the receiver and the given source tree,
using the given comparer to compare data objects.
The result describes the changes which, if assembled with the receiver,
will produce the given source tree.
In more detail, let c = a.forwardDeltaWith(b).
c has the same content as b, but is represented as a delta tree with a as the parent.
Also, c is immutable.
There is no requirement that a and b be related, although it is usually more
efficient if they are. The node keys are used as the basis of correlation
between trees.
Note that if b is already represented as a delta over a,
then c will have the same internal structure as b.
Thus the very common case of previous forwardDeltaWith: current
is actually very fast when current is a modification of previous.
Params: sourceTree – second delta tree to create a delta between
comparer – the comparer used to compare data objects
Returns: the new delta/**
	 * Returns a forward delta between the receiver and the given source tree,
	 * using the given comparer to compare data objects.
	 * The result describes the changes which, if assembled with the receiver,
	 * will produce the given source tree.
	 * In more detail, let c = a.forwardDeltaWith(b).
	 * c has the same content as b, but is represented as a delta tree with a as the parent.
	 * Also, c is immutable.
	 *
	 * There is no requirement that a and b be related, although it is usually more
	 * efficient if they are. The node keys are used as the basis of correlation
	 * between trees.
	 *
	 * Note that if b is already represented as a delta over a,
	 * then c will have the same internal structure as b.
	 * Thus the very common case of previous forwardDeltaWith: current
	 * is actually very fast when current is a modification of previous.
	 *
	 * @param sourceTree second delta tree to create a delta between
	 * @param comparer the comparer used to compare data objects
	 * @return the new delta
	 */
	public DeltaDataTree forwardDeltaWith(DeltaDataTree sourceTree, IComparator comparer) {
		DeltaDataTree newTree;
		if (this == sourceTree) {
			newTree = this.newEmptyDeltaTree();
		} else if (sourceTree.hasAncestor(this)) {
			AbstractDataTreeNode assembled = sourceTree.getRootNode();
			DeltaDataTree treeParent = sourceTree;

			/* Iterate through the sourceTree's ancestors until the receiver is reached */
			while ((treeParent = treeParent.getParent()) != this) {
				assembled = treeParent.getRootNode().assembleWith(assembled);
			}
			newTree = new DeltaDataTree(assembled, this);
			newTree.simplify(comparer);
		} else if (this.hasAncestor(sourceTree)) {
			//create the delta backwards and then reverse it
			newTree = sourceTree.forwardDeltaWith(this, comparer);
			newTree = newTree.asBackwardDelta();
		} else {
			DataTreeNode thisCompleteRoot = (DataTreeNode) this.copyCompleteSubtree(rootKey());
			DataTreeNode sourceTreeCompleteRoot = (DataTreeNode) sourceTree.copyCompleteSubtree(rootKey());
			AbstractDataTreeNode deltaRoot = thisCompleteRoot.forwardDeltaWith(sourceTreeCompleteRoot, comparer);
			newTree = new DeltaDataTree(deltaRoot, this);
		}
		newTree.immutable();
		return newTree;
	}

	See Also: getChildCount.getChildCount(IPath)/**
	 * @see AbstractDataTree#getChildCount(IPath)
	 */
	@Override
	public int getChildCount(IPath parentKey) {
		return getChildNodes(parentKey).length;
	}

	Returns the child nodes of a node in the tree.
/**
	 * Returns the child nodes of a node in the tree.
	 */
	protected AbstractDataTreeNode[] getChildNodes(IPath parentKey) {

		/* Algorithm:
		 *   for each delta in chain (going backwards),
		 *     get list of child nodes, if any in delta
		 *     assemble with previously seen list, if any
		 *     break when complete tree found,
		 *   report error if parent is missing or has been deleted
		 */

		AbstractDataTreeNode[] childNodes = null;
		int keyLength = parentKey.segmentCount();
		for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
			AbstractDataTreeNode node = tree.rootNode;
			boolean complete = !node.isDelta();
			for (int i = 0; i < keyLength; i++) {
				node = node.childAtOrNull(parentKey.segment(i));
				if (node == null) {
					break;
				}
				if (!node.isDelta()) {
					complete = true;
				}
			}
			if (node != null) {
				if (node.isDeleted()) {
					break;
				}
				if (childNodes == null) {
					childNodes = node.children;
				} else {
					// Be sure to assemble(old, new) rather than (new, old).
					// Keep deleted nodes if we haven't encountered the complete node yet.
					childNodes = AbstractDataTreeNode.assembleWith(node.children, childNodes, !complete);
				}
			}
			if (complete) {
				if (childNodes != null) {
					return childNodes;
				}
				// Not found, but complete node encountered, so should not check parent tree.
				break;
			}
		}
		if (childNodes != null) {
			// Some deltas carry info about children, but there is
			// no complete node against which they describe deltas.
			Assert.isTrue(false, Messages.dtree_malformedTree);
		}

		// Node is missing or has been deleted.
		handleNotFound(parentKey);
		return null;//should not get here
	}

	See Also: getChildren.getChildren(IPath)/**
	 * @see AbstractDataTree#getChildren(IPath)
	 */
	@Override
	public IPath[] getChildren(IPath parentKey) {
		AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
		int len = childNodes.length;
		if (len == 0)
			return NO_CHILDREN;
		IPath[] answer = new IPath[len];
		for (int i = 0; i < len; ++i)
			answer[i] = parentKey.append(childNodes[i].name);
		return answer;
	}

	Returns the data at a node of the tree.
Params: key – 
key of node for which to return data./**
	 * Returns the data at a node of the tree.
	 *
	 * @param key
	 *	key of node for which to return data.
	 */
	@Override
	public Object getData(IPath key) {

		/* Algorithm:
		 *   for each delta in chain (going backwards),
		 *     get node, if any in delta
		 *	   if it carries data, return it
		 *     break when complete tree found
		 *   report error if node is missing or has been deleted
		 */

		int keyLength = key.segmentCount();
		for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
			AbstractDataTreeNode node = tree.rootNode;
			boolean complete = !node.isDelta();
			for (int i = 0; i < keyLength; i++) {
				node = node.childAtOrNull(key.segment(i));
				if (node == null) {
					break;
				}
				if (!node.isDelta()) {
					complete = true;
				}
			}
			if (node != null) {
				if (node.hasData()) {
					return node.getData();
				} else if (node.isDeleted()) {
					break;
				}
			}
			if (complete) {
				// Not found, but complete node encountered, so should not check parent tree.
				break;
			}
		}
		handleNotFound(key);
		return null; //can't get here
	}

	See Also: getNameOfChild.getNameOfChild(IPath, int)/**
	 * @see AbstractDataTree#getNameOfChild(IPath, int)
	 */
	@Override
	public String getNameOfChild(IPath parentKey, int index) {
		AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
		return childNodes[index].name;
	}

	Returns the local names for the children of a node of the tree.
See Also: getNamesOfChildren.getNamesOfChildren(IPath)/**
	 * Returns the local names for the children of a node of the tree.
	 *
	 * @see AbstractDataTree#getNamesOfChildren(IPath)
	 */
	@Override
	public String[] getNamesOfChildren(IPath parentKey) {
		AbstractDataTreeNode[] childNodes = getChildNodes(parentKey);
		int len = childNodes.length;
		String[] namesOfChildren = new String[len];
		for (int i = 0; i < len; ++i)
			namesOfChildren[i] = childNodes[i].name;
		return namesOfChildren;
	}

	Returns the parent of the tree.
/**
	 * Returns the parent of the tree.
	 */
	public DeltaDataTree getParent() {
		return parent;
	}

	Returns the root node of the tree.
/**
	 * Returns the root node of the tree.
	 */
	@Override
	protected AbstractDataTreeNode getRootNode() {
		return rootNode;
	}

	Returns true if the receiver's parent has the specified ancestor
Params: ancestor – the ancestor in question/**
	 * Returns true if the receiver's parent has the specified ancestor
	 *
	 * @param ancestor the ancestor in question
	 */
	protected boolean hasAncestor(DeltaDataTree ancestor) {
		DeltaDataTree myParent = this;
		while ((myParent = myParent.getParent()) != null) {
			if (myParent == ancestor) {
				return true;
			}
		}
		return false;
	}

	Returns true if the receiver includes a node with
the given key, false otherwise.
/**
	 * Returns true if the receiver includes a node with
	 * the given key, false otherwise.
	 */
	@Override
	public boolean includes(IPath key) {
		return searchNodeAt(key) != null;
	}

	public boolean isEmptyDelta() {
		return rootNode.getChildren().length == 0;
	}

	Returns an object containing:
 - the node key
	- a flag indicating whether the specified node was found
 - the data for the node, if it was found
Params: key –  key of node for which we want to retrieve data./**
	 * Returns an object containing:
	 *  - the node key
	 * 	- a flag indicating whether the specified node was found
	 *  - the data for the node, if it was found
	 *
	 * @param key  key of node for which we want to retrieve data.
	 */
	@Override
	public DataTreeLookup lookup(IPath key) {
		int keyLength = key.segmentCount();
		for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
			AbstractDataTreeNode node = tree.rootNode;
			boolean complete = !node.isDelta();
			for (int i = 0; i < keyLength; i++) {
				node = node.childAtOrNull(key.segment(i));
				if (node == null) {
					break;
				}
				complete |= !node.isDelta();
			}
			if (node != null) {
				if (node.hasData()) {
					return DataTreeLookup.newLookup(key, true, node.getData(), tree == this);
				} else if (node.isDeleted()) {
					break;
				}
			}
			if (complete) {
				// Not found, but complete node encountered, so should not check parent tree.
				break;
			}
		}
		return DataTreeLookup.newLookup(key, false, null);
	}

	Returns an object containing:
 - the node key
	- a flag indicating whether the specified node was found
 - the data for the node, if it was found
This is a case-insensitive variant of the lookup
method.
Params: key –  key of node for which we want to retrieve data./**
	 * Returns an object containing:
	 *  - the node key
	 * 	- a flag indicating whether the specified node was found
	 *  - the data for the node, if it was found
	 *
	 * This is a case-insensitive variant of the <code>lookup</code>
	 * method.
	 *
	 * @param key  key of node for which we want to retrieve data.
	 */
	public DataTreeLookup lookupIgnoreCase(IPath key) {
		int keyLength = key.segmentCount();
		for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
			AbstractDataTreeNode node = tree.rootNode;
			boolean complete = !node.isDelta();
			for (int i = 0; i < keyLength; i++) {
				node = node.childAtIgnoreCase(key.segment(i));
				if (node == null) {
					break;
				}
				complete |= !node.isDelta();
			}
			if (node != null) {
				if (node.hasData()) {
					return DataTreeLookup.newLookup(key, true, node.getData(), tree == this);
				} else if (node.isDeleted()) {
					break;
				}
			}
			if (complete) {
				// Not found, but complete node encountered, so should not check parent tree.
				break;
			}
		}
		return DataTreeLookup.newLookup(key, false, null);
	}

	Converts this tree's representation to be a complete tree, not a delta.
This disconnects this tree from its parents.
The parent trees are unaffected.
/**
	 * Converts this tree's representation to be a complete tree, not a delta.
	 * This disconnects this tree from its parents.
	 * The parent trees are unaffected.
	 */
	public void makeComplete() {
		AbstractDataTreeNode assembled = getRootNode();
		DeltaDataTree myParent = getParent();
		while (myParent != null) {
			assembled = myParent.getRootNode().assembleWith(assembled);
			myParent = myParent.getParent();
		}
		setRootNode(assembled);
		setParent(null);
	}

	Returns a complete node containing the contents of the subtree
rooted at key in the receiver.  Uses the public API.
Params: key – 
key of subtree whose contents we want to copy./**
	 * Returns a complete node containing the contents of the subtree
	 * rooted at <code>key</code> in the receiver.  Uses the public API.
	 *
	 * @param key
	 *	key of subtree whose contents we want to copy.
	 */
	protected AbstractDataTreeNode naiveCopyCompleteSubtree(IPath key) {
		String[] childNames = getNamesOfChildren(key);
		int numChildren = childNames.length;
		AbstractDataTreeNode[] childNodes;
		if (numChildren == 0) {
			childNodes = AbstractDataTreeNode.NO_CHILDREN;
		} else {
			childNodes = new AbstractDataTreeNode[numChildren];
			/* do for each child */
			for (int i = numChildren; --i >= 0;) {
				childNodes[i] = copyCompleteSubtree(key.append(childNames[i]));
			}
		}
		return new DataTreeNode(key.lastSegment(), getData(key), childNodes);
	}

	Returns a new tree which represents an empty, mutable delta on the
receiver.  It is not possible to obtain a new delta tree if the receiver is
not immutable, as subsequent changes to the receiver would affect the
resulting delta.
/**
	 * Returns a new tree which represents an empty, mutable delta on the
	 * receiver.  It is not possible to obtain a new delta tree if the receiver is
	 * not immutable, as subsequent changes to the receiver would affect the
	 * resulting delta.
	 */
	public DeltaDataTree newEmptyDeltaTree() {
		if (!isImmutable())
			throw new IllegalArgumentException(Messages.dtree_notImmutable);
		DeltaDataTree newTree = (DeltaDataTree) this.copy();
		newTree.setParent(this);
		newTree.emptyDelta();
		return newTree;
	}

	Makes the receiver the root tree in the list of trees on which it is based.
The receiver's representation becomes a complete tree, while its parents'
representations become backward deltas based on the receiver.
It is not possible to re-root a source tree that is not immutable, as this
would require that its parents be expressed as deltas on a source tree
which could still change.
Throws: RuntimeException – 
receiver is not immutable/**
	 * Makes the receiver the root tree in the list of trees on which it is based.
	 * The receiver's representation becomes a complete tree, while its parents'
	 * representations become backward deltas based on the receiver.
	 * It is not possible to re-root a source tree that is not immutable, as this
	 * would require that its parents be expressed as deltas on a source tree
	 * which could still change.
	 *
	 * @exception RuntimeException
	 *	receiver is not immutable
	 */
	public DeltaDataTree reroot() {
		/* self mutex critical region */
		reroot(this);
		return this;
	}

	Makes the given source tree the root tree in the list of trees on which it is based.
The source tree's representation becomes a complete tree, while its parents'
representations become backward deltas based on the source tree.
It is not possible to re-root a source tree that is not immutable, as this
would require that its parents be expressed as deltas on a source tree
which could still change.
Params: sourceTree – 
source tree to set as the new root
Throws: RuntimeException – 
sourceTree is not immutable/**
	 * Makes the given source tree the root tree in the list of trees on which it is based.
	 * The source tree's representation becomes a complete tree, while its parents'
	 * representations become backward deltas based on the source tree.
	 * It is not possible to re-root a source tree that is not immutable, as this
	 * would require that its parents be expressed as deltas on a source tree
	 * which could still change.
	 *
	 * @param sourceTree
	 *	source tree to set as the new root
	 * @exception RuntimeException
	 *	sourceTree is not immutable
	 */
	protected void reroot(DeltaDataTree sourceTree) {
		if (!sourceTree.isImmutable())
			handleImmutableTree();
		DeltaDataTree sourceParent = sourceTree.getParent();
		if (sourceParent == null)
			return;
		this.reroot(sourceParent);
		DeltaDataTree backwardDelta = sourceTree.asBackwardDelta();
		DeltaDataTree complete = sourceParent.assembleWithForwardDelta(sourceTree);
		sourceTree.setRootNode(complete.getRootNode());
		sourceTree.setParent(null);
		sourceParent.setRootNode(backwardDelta.getRootNode());
		sourceParent.setParent(sourceTree);
	}

	Returns a complete node containing the contents of a subtree of the tree.
Returns null  if the node at this key does not exist.  This is a thread-safe
version of copyCompleteSubtree
Params: key – key of subtree to copy/**
	 * Returns a complete node containing the contents of a subtree of the tree.
	 * Returns null  if the node at this key does not exist.  This is a thread-safe
	 * version of copyCompleteSubtree
	 *
	 * @param key key of subtree to copy
	 */
	public AbstractDataTreeNode safeCopyCompleteSubtree(IPath key) {
		AbstractDataTreeNode node = searchNodeAt(key);
		if (node == null)
			return null;
		if (node.isDelta())
			return safeNaiveCopyCompleteSubtree(key);
		//copy the node in case the user wants to hammer the subtree name
		return node.copy();
	}

	Returns a complete node containing the contents of the subtree
rooted at @key in the receiver.  Returns null if this node does not exist in
the tree.  This is a thread-safe version of naiveCopyCompleteSubtree
Params: key – 
key of subtree whose contents we want to copy./**
	 * Returns a complete node containing the contents of the subtree
	 * rooted at @key in the receiver.  Returns null if this node does not exist in
	 * the tree.  This is a thread-safe version of naiveCopyCompleteSubtree
	 *
	 * @param key
	 *	key of subtree whose contents we want to copy.
	 */
	protected AbstractDataTreeNode safeNaiveCopyCompleteSubtree(IPath key) {
		try {
			String[] childNames = getNamesOfChildren(key);
			int numChildren = childNames.length;
			AbstractDataTreeNode[] childNodes;
			if (numChildren == 0) {
				childNodes = AbstractDataTreeNode.NO_CHILDREN;
			} else {
				childNodes = new AbstractDataTreeNode[numChildren];
				/* do for each child */
				int actualChildCount = 0;
				for (int i = numChildren; --i >= 0;) {
					childNodes[i] = safeCopyCompleteSubtree(key.append(childNames[i]));
					if (childNodes[i] != null)
						actualChildCount++;
				}
				//if there are less actual children due to concurrent deletion, shrink the child array
				if (actualChildCount < numChildren) {
					AbstractDataTreeNode[] actualChildNodes = new AbstractDataTreeNode[actualChildCount];
					for (int iOld = 0, iNew = 0; iOld < numChildren; iOld++)
						if (childNodes[iOld] != null)
							actualChildNodes[iNew++] = childNodes[iOld];
					childNodes = actualChildNodes;
				}
			}
			return new DataTreeNode(key.lastSegment(), getData(key), childNodes);
		} catch (ObjectNotFoundException e) {
			return null;
		}
	}

	Returns the specified node.  Search in the parent if necessary.  Return null
if the node is not found or if it has been deleted
/**
	 * Returns the specified node.  Search in the parent if necessary.  Return null
	 * if the node is not found or if it has been deleted
	 */
	protected AbstractDataTreeNode searchNodeAt(IPath key) {
		int keyLength = key.segmentCount();
		for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
			AbstractDataTreeNode node = tree.rootNode;
			boolean complete = !node.isDelta();
			for (int i = 0; i < keyLength; i++) {
				node = node.childAtOrNull(key.segment(i));
				if (node == null) {
					break;
				}
				if (!node.isDelta()) {
					complete = true;
				}
			}
			if (node != null) {
				if (node.isDeleted())
					break;
				return node;
			}
			if (complete) {
				// Not found, but complete node encountered, so should not check parent tree.
				break;
			}
		}
		return null;
	}

	See Also: setData.setData(IPath, Object)/**
	 * @see AbstractDataTree#setData(IPath, Object)
	 */
	@Override
	public void setData(IPath key, Object data) {
		if (isImmutable())
			handleImmutableTree();
		if (!includes(key))
			handleNotFound(key);
		assembleNode(key, new DataDeltaNode(key.lastSegment(), data));
	}

	Sets the parent of the tree.
/**
	 * Sets the parent of the tree.
	 */
	protected void setParent(DeltaDataTree aTree) {
		parent = aTree;
	}

	Sets the root node of the tree
/**
	 * Sets the root node of the tree
	 */
	@Override
	void setRootNode(AbstractDataTreeNode aNode) {
		rootNode = aNode;
	}

	Simplifies the receiver:
- replaces any DataDelta nodes with the same data as the parent
  with a NoDataDelta node
- removes any empty (leaf NoDataDelta) nodes
/**
	 * Simplifies the receiver:
	 *	- replaces any DataDelta nodes with the same data as the parent
	 *	  with a NoDataDelta node
	 *	- removes any empty (leaf NoDataDelta) nodes
	 */
	protected void simplify(IComparator comparer) {
		if (parent == null)
			return;
		setRootNode(rootNode.simplifyWithParent(rootKey(), parent, comparer));
	}

	See Also: shareStrings.shareStrings(StringPool)/**
	 * @see org.eclipse.core.internal.utils.IStringPoolParticipant#shareStrings(StringPool)
	 */
	public void storeStrings(StringPool set) {
		AbstractDataTreeNode root = null;
		for (DeltaDataTree dad = this; dad != null; dad = dad.getParent()) {
			root = dad.getRootNode();
			if (root != null)
				root.storeStrings(set);
		}
	}
}
Params:	sourceTree – second delta tree to create a delta between comparer – the comparer used to compare data objects
Returns:	the new delta
Params:	sourceTree – source tree to set as the new root
Throws:	RuntimeException – sourceTree is not immutable
/

org.eclipse.platform/ org.eclipse.core.resources/ 3.13.600/ org/eclipse/core/internal/dtree/DeltaDataTree.java
