| /******************************************************************************* |
| * 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 <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. |
| */ |
| public DeltaDataTree() { |
| this.empty(); |
| } |
| |
| /** |
| * 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. |
| * |
| * @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. |
| */ |
| 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. |
| */ |
| 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 (int i = 0; i < children.length; i++) { |
| AbstractDataTreeNode newChild = children[i].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). |
| * |
| * @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. |
| * |
| * <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. |
| */ |
| 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. |
| * |
| * <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. |
| */ |
| 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. |
| */ |
| 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. |
| */ |
| @Override |
| protected AbstractDataTree copy() { |
| return new DeltaDataTree(rootNode, parent); |
| } |
| |
| /** |
| * 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 AbstractDataTree#createChild(IPath, String) |
| */ |
| @Override |
| public void createChild(IPath parentKey, String localName) { |
| createChild(parentKey, localName, null); |
| } |
| |
| /** |
| * @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). |
| */ |
| static DeltaDataTree createEmptyDelta() { |
| |
| DeltaDataTree newTree = new DeltaDataTree(); |
| newTree.emptyDelta(); |
| return newTree; |
| } |
| |
| /** |
| * Creates and returns an instance of the receiver. |
| * @see AbstractDataTree#createInstance() |
| */ |
| @Override |
| protected AbstractDataTree createInstance() { |
| return new DeltaDataTree(); |
| } |
| |
| /** |
| * @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 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 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. |
| */ |
| void emptyDelta() { |
| rootNode = new NoDataDeltaNode(null); |
| } |
| |
| /** |
| * 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. |
| * |
| * @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 AbstractDataTree#getChildCount(IPath) |
| */ |
| @Override |
| public int getChildCount(IPath parentKey) { |
| return getChildNodes(parentKey).length; |
| } |
| |
| /** |
| * 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 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. |
| * |
| * @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 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 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. |
| */ |
| public DeltaDataTree getParent() { |
| return parent; |
| } |
| |
| /** |
| * Returns the root node of the tree. |
| */ |
| @Override |
| protected AbstractDataTreeNode getRootNode() { |
| return rootNode; |
| } |
| |
| /** |
| * 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. |
| */ |
| @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 |
| * |
| * @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 <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. |
| */ |
| 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 <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. |
| */ |
| 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. |
| * |
| * @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. |
| * |
| * @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 |
| * |
| * @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 |
| * |
| * @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 |
| */ |
| 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 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. |
| */ |
| protected void setParent(DeltaDataTree aTree) { |
| parent = aTree; |
| } |
| |
| /** |
| * 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 |
| */ |
| protected void simplify(IComparator comparer) { |
| if (parent == null) |
| return; |
| setRootNode(rootNode.simplifyWithParent(rootKey(), parent, comparer)); |
| } |
| |
| /** |
| * @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); |
| } |
| } |
| } |