org.eclipse.core.internal.dtree
Class DeltaDataTree

java.lang.Object
  org.eclipse.core.internal.dtree.AbstractDataTree
      org.eclipse.core.internal.dtree.DeltaDataTree

public class DeltaDataTree
extends AbstractDataTree

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.

Constructor Summary

DeltaDataTree()
Creates a new empty tree.

DeltaDataTree(AbstractDataTreeNode rootNode)
Creates a new tree.

Method Summary

DeltaDataTree	asReverseComparisonTree(IComparator comparator) This method can only be called on a comparison tree created using DeltaDataTree.compareWith().
DeltaDataTree	assembleWithForwardDelta(DeltaDataTree deltaTree) Assembles the receiver with the given delta tree and answer the resulting, mutable source tree.
DeltaDataTree	collapseTo(DeltaDataTree collapseTo, IComparator comparator) Collapses this tree so that the given ancestor becomes its immediate parent.
DeltaDataTree	compareWith(DeltaDataTree other, IComparator comparator) Returns a DeltaDataTree that describes the differences between this tree and "other" tree.
DeltaDataTree	compareWith(DeltaDataTree other, IComparator comparator, org.eclipse.core.runtime.IPath path) Compares this tree with another tree, starting from the given path.
AbstractDataTreeNode	copyCompleteSubtree(org.eclipse.core.runtime.IPath key) Returns a complete node containing the contents of a subtree of the tree.
void	createChild(org.eclipse.core.runtime.IPath parentKey, java.lang.String localName) Creates a new child in the tree.
void	createChild(org.eclipse.core.runtime.IPath parentKey, java.lang.String localName, java.lang.Object data) Creates a new child in the tree.
void	createSubtree(org.eclipse.core.runtime.IPath key, AbstractDataTreeNode node) Creates or replaces a subtree in the tree.
void	deleteChild(org.eclipse.core.runtime.IPath parentKey, java.lang.String localName) Deletes a child from the tree.
void	empty() Initializes the receiver so that it is a complete, empty tree.
AbstractDataTreeNode	findNodeAt(org.eclipse.core.runtime.IPath key) Returns a node of the tree if it is present, otherwise returns null
DeltaDataTree	forwardDeltaWith(DeltaDataTree sourceTree, IComparator comparer) Returns a forward delta between the receiver and the given source tree, using the given comparer to compare data objects.
int	getChildCount(org.eclipse.core.runtime.IPath parentKey) Returns the number of children of a node
org.eclipse.core.runtime.IPath[]	getChildren(org.eclipse.core.runtime.IPath parentKey) Returns the keys of all children of a node.
java.lang.Object	getData(org.eclipse.core.runtime.IPath key) Returns the data at a node of the tree.
java.lang.String	getNameOfChild(org.eclipse.core.runtime.IPath parentKey, int index) Returns the local name of a node in the tree
java.lang.String[]	getNamesOfChildren(org.eclipse.core.runtime.IPath parentKey) Returns the local names for the children of a node of the tree.
DeltaDataTree	getParent() Returns the parent of the tree.
boolean	includes(org.eclipse.core.runtime.IPath key) Returns true if the receiver includes a node with the given key, false otherwise.
boolean	isEmptyDelta()
DataTreeLookup	lookup(org.eclipse.core.runtime.IPath key) 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
DataTreeLookup	lookupIgnoreCase(org.eclipse.core.runtime.IPath key) 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.
void	makeComplete() Converts this tree's representation to be a complete tree, not a delta.
DeltaDataTree	newEmptyDeltaTree() Returns a new tree which represents an empty, mutable delta on the receiver.
DeltaDataTree	reroot() Makes the receiver the root tree in the list of trees on which it is based.
AbstractDataTreeNode	safeCopyCompleteSubtree(org.eclipse.core.runtime.IPath key) Returns a complete node containing the contents of a subtree of the tree.
void	setData(org.eclipse.core.runtime.IPath key, java.lang.Object data) Sets the data of a node.
void	storeStrings(StringPool set)

Methods inherited from class org.eclipse.core.internal.dtree.AbstractDataTree

getChild, immutable, isImmutable, rootKey

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DeltaDataTree

public DeltaDataTree()

Creates a new empty tree.

DeltaDataTree

public DeltaDataTree(AbstractDataTreeNode rootNode)

Creates a new tree.

Parameters:

rootNode - root node of new tree.

Method Detail

asReverseComparisonTree

public DeltaDataTree asReverseComparisonTree(IComparator comparator)

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.

assembleWithForwardDelta

public DeltaDataTree assembleWithForwardDelta(DeltaDataTree deltaTree)

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

collapseTo

public DeltaDataTree collapseTo(DeltaDataTree collapseTo,
                                IComparator comparator)

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.

compareWith

public DeltaDataTree compareWith(DeltaDataTree other,
                                 IComparator comparator)

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.

compareWith

public DeltaDataTree compareWith(DeltaDataTree other,
                                 IComparator comparator,
                                 org.eclipse.core.runtime.IPath path)

Compares this tree with another tree, starting from the given path. The given path will be the root node of the returned tree.

copyCompleteSubtree

public AbstractDataTreeNode copyCompleteSubtree(org.eclipse.core.runtime.IPath key)

Returns a complete node containing the contents of a subtree of the tree.

Specified by:

copyCompleteSubtree in class AbstractDataTree

Parameters:

key - key of subtree to copy

createChild

public void createChild(org.eclipse.core.runtime.IPath parentKey,
                        java.lang.String localName)

Description copied from class: AbstractDataTree

Creates a new child in the tree. If a child with such a name exists, it is replaced with the new child

Specified by:

createChild in class AbstractDataTree

Parameters:

parentKey - key of parent for new child.

localName - name for new child.

See Also:

AbstractDataTree.createChild(IPath, String)

createChild

public void createChild(org.eclipse.core.runtime.IPath parentKey,
                        java.lang.String localName,
                        java.lang.Object data)

Description copied from class: AbstractDataTree

Creates a new child in the tree. If a child with such a name exists, it is replaced with the new child

Specified by:

createChild in class AbstractDataTree

Parameters:

parentKey - key of parent for new child.

localName - name for new child.

data - the data for the new child

See Also:

AbstractDataTree.createChild(IPath, String, Object)

createSubtree

public void createSubtree(org.eclipse.core.runtime.IPath key,
                          AbstractDataTreeNode node)

Description copied from class: AbstractDataTree

Creates or replaces a subtree in the tree. The parent node must exist.

Specified by:

createSubtree in class AbstractDataTree

Parameters:

key - key of parent of subtree to create/replace

node - new subtree to add to tree

See Also:

AbstractDataTree.createSubtree(IPath, AbstractDataTreeNode)

deleteChild

public void deleteChild(org.eclipse.core.runtime.IPath parentKey,
                        java.lang.String localName)

Description copied from class: AbstractDataTree

Deletes a child from the tree.

Note: this method requires both parentKey and localName, making it impossible to delete the root node.

Specified by:

deleteChild in class AbstractDataTree

Parameters:

parentKey - parent of node to delete.

localName - name of node to delete.

See Also:

AbstractDataTree.deleteChild(IPath, String)

empty

public void empty()

Initializes the receiver so that it is a complete, empty tree.

Specified by:

empty in class AbstractDataTree

See Also:

AbstractDataTree.empty()

findNodeAt

public AbstractDataTreeNode findNodeAt(org.eclipse.core.runtime.IPath key)

Returns a node of the tree if it is present, otherwise returns null

Parameters:

key - key of node to find

forwardDeltaWith

public DeltaDataTree forwardDeltaWith(DeltaDataTree sourceTree,
                                      IComparator comparer)

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.

Parameters:

sourceTree - second delta tree to create a delta between

comparer - the comparer used to compare data objects

Returns:

the new delta

getChildCount

public int getChildCount(org.eclipse.core.runtime.IPath parentKey)

Description copied from class: AbstractDataTree

Returns the number of children of a node

Overrides:

getChildCount in class AbstractDataTree

Parameters:

parentKey - key of the node for which we want to retreive the number of children

See Also:

AbstractDataTree.getChildCount(IPath)

getChildren

public org.eclipse.core.runtime.IPath[] getChildren(org.eclipse.core.runtime.IPath parentKey)

Description copied from class: AbstractDataTree

Returns the keys of all children of a node.

Overrides:

getChildren in class AbstractDataTree

Parameters:

parentKey - key of parent whose children we want to retrieve.

See Also:

AbstractDataTree.getChildren(IPath)

getData

public java.lang.Object getData(org.eclipse.core.runtime.IPath key)

Returns the data at a node of the tree.

Specified by:

getData in class AbstractDataTree

Parameters:

key - key of node for which to return data.

getNameOfChild

public java.lang.String getNameOfChild(org.eclipse.core.runtime.IPath parentKey,
                                       int index)

Description copied from class: AbstractDataTree

Returns the local name of a node in the tree

Overrides:

getNameOfChild in class AbstractDataTree

Parameters:

parentKey - parent of node whose name we want to retrieve

index - index of node in its parent

See Also:

AbstractDataTree.getNameOfChild(IPath, int)

getNamesOfChildren

public java.lang.String[] getNamesOfChildren(org.eclipse.core.runtime.IPath parentKey)

Returns the local names for the children of a node of the tree.

Specified by:

getNamesOfChildren in class AbstractDataTree

Parameters:

parentKey - key of node whose children we want to retrieve

See Also:

AbstractDataTree.getNamesOfChildren(IPath)

getParent

public DeltaDataTree getParent()

Returns the parent of the tree.

includes

public boolean includes(org.eclipse.core.runtime.IPath key)

Returns true if the receiver includes a node with the given key, false otherwise.

Specified by:

includes in class AbstractDataTree

Parameters:

key - key of node to find

isEmptyDelta

public boolean isEmptyDelta()

lookup

public DataTreeLookup lookup(org.eclipse.core.runtime.IPath key)

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

Specified by:

lookup in class AbstractDataTree

Parameters:

key - key of node for which we want to retrieve data.

lookupIgnoreCase

public DataTreeLookup lookupIgnoreCase(org.eclipse.core.runtime.IPath key)

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.

Parameters:

key - key of node for which we want to retrieve data.

makeComplete

public void makeComplete()

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.

newEmptyDeltaTree

public DeltaDataTree newEmptyDeltaTree()

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.

reroot

public DeltaDataTree reroot()

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:

java.lang.RuntimeException - receiver is not immutable

safeCopyCompleteSubtree

public AbstractDataTreeNode safeCopyCompleteSubtree(org.eclipse.core.runtime.IPath key)

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

Parameters:

key - key of subtree to copy

setData

public void setData(org.eclipse.core.runtime.IPath key,
                    java.lang.Object data)

Description copied from class: AbstractDataTree

Sets the data of a node.

Specified by:

setData in class AbstractDataTree

Parameters:

key - key of node for which to set data

data - new data value for node

See Also:

AbstractDataTree.setData(IPath, Object)

storeStrings

public void storeStrings(StringPool set)