edu.stanford.nlp.trees
Class Tree

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--edu.stanford.nlp.trees.Tree

All Implemented Interfaces:

Collection, Labeled, Scored

Direct Known Subclasses:

LabeledScoredTreeLeaf, LabeledScoredTreeNode, SimpleTree

public abstract class Tree

extends AbstractCollection

implements Labeled, Scored

The abstract class Tree is used to collect all of the tree types, and acts as a generic composite type. This is the standard implementation of inheritance-based polymorphism. Trees, like standard containers, are not parametrized in any way by the type of object in the data field. All Tree objects support accessors for their children (a Tree[]), their data (a Label), and their score (a double). However, different concrete implementations may or may not include the latter two, in which case a default value is returned. The class Tree defines no data fields. The three abstract methods that must be implemented are: children(), setChildren(Tree[]), and treeFactory(). There is now support for finding the parent of a tree. This may be done by search from a tree root, or via a directly stored parent. The Tree class now implements the Collection interface: in terms of this, each node of the tree is an element of the collection; hence one can explore the tree by using the methods of this interface. A Tree is regarded as a read-only Collection (even though the Tree class has various methods that modify trees). Moreover, the implementation is not thread-safe: no attempt is made to detect and report concurrent modifications.

Constructor Summary

Tree()

Method Summary

abstract Tree[]	children() Returns an array of children for the current node.
Set	constituents() Returns the Constituents generated by the parse tree.
Set	constituents(ConstituentFactory cf) Returns the Constituents generated by the parse tree.
Tree	deepCopy() Create a deep copy of the tree.
Tree	deepCopy(TreeFactory tf) Create a deep copy of the tree.
int	depth() Finds the depth of the tree.
Tree	firstChild() Returns the first child of a tree, or null if none
List	getChildrenAsList() Returns an array of children for the current node.
void	indentedListPrint() Indented list printing of a tree.
void	indentedListPrint(String indent, String pad) Indented list printing of a tree with each line indented
boolean	isLeaf() Returns true if the tree is a leaf, false otherwise.
boolean	isPreTerminal() Return whether this node is a preterminal or not.
Iterator	iterator() Returns an iterator over the nodes of the tree.
Label	label() Returns the label associated with the current node, or null if there is no label.
Collection	labels() Get the set of all node and leaf Labels, null or otherwise, contained in the tree.
Tree	lastChild() Returns the last child of a tree, or null if none
Tree	parent() Return the parent of the tree node.
Tree	parent(Tree root) Return the parent of the tree node.
void	pennPrint() Print the tree as done in Penn Treebank merged files.
void	pennPrint(PrintStream ps) Print the tree as done in Penn Treebank merged files.
void	percolateHeads(HeadFinder hf) Finds the heads of the tree.
List	preTerminalYield() Gets the preterminal yield (i.e., tags) of the tree.
List	preTerminalYield(List y) Gets the preterminal yield (i.e., tags) of the tree.
Tree	prune(Filter filter) Creates a deep copy of the tree, where all nodes that the filter does not accept and all children of such nodes are pruned.
Tree	prune(Filter filter, TreeFactory tf) Creates a deep copy of the tree, where all nodes that the filter does not accept and all children of such nodes are pruned.
double	score() Returns the score associated with the current node, or NaN if there is no score.
void	setChildren(List childTreesList) Set the children of this tree node to the given list.
abstract void	setChildren(Tree[] children) Set the children of this node to be the children given in the array.
void	setLabel(Label label) Sets the label associated with the current node, if there is one.
void	setLabels(Collection c) Sets the labels associated with this object.
void	setScore(double score) Sets the score associated with the current node, if there is one
int	size() Returns the number of nodes the tree contains.
Tree	spliceOut(Filter nodeFilter) Creates a (partial) deep copy of the tree, where all nodes that the filter does not accept are spliced out.
Tree	spliceOut(Filter nodeFilter, TreeFactory tf) Creates a (partial) deep copy of the tree, where all nodes that the filter does not accept are spliced out.
Set	subTrees() Get the set of all subtrees inside the tree by returning a tree rooted at each node.
Set	subTrees(Set n) Add the set of all subtrees inside a tree to the given Set.
Sentence	taggedYield() Gets the tagged yield of the tree.
List	taggedYield(List ty) Gets the tagged yield of the tree -- that is, get the preterminals as well as the terminals.
String	toString() Converts parse tree to string in Penn Treebank format.
StringBuffer	toStringBuffer(StringBuffer sb) Appends the printed form of a parse tree (as a bracketed String) to a StringBuffer.
Tree	transform(TreeTransformer transformer) Create a transformed Tree.
Tree	transform(TreeTransformer transformer, TreeFactory tf) Create a transformed Tree.
abstract TreeFactory	treeFactory() Return a TreeFactory that produces trees of the appropriate type.
Sentence	yield() Gets the yield of the tree.
List	yield(List y) Gets the yield of the tree.

Methods inherited from class java.util.AbstractCollection

add, addAll, clear, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

Tree

public Tree()

Method Detail

isLeaf

public boolean isLeaf()

Returns true if the tree is a leaf, false otherwise. Can be used on an arbitrary Tree. Being a leaf is defined as having no children. This is the preferred alternative to running meta checks on types, as it works independent of Tree implementation. If those isLeaf methods are final, it will be very efficient, too.

isPreTerminal

public boolean isPreTerminal()

Return whether this node is a preterminal or not. A preterminal is defined to be a node with one child which is itself a leaf.

Returns:

true if the node is a preterminal; false otherwise

children

public abstract Tree[] children()

Returns an array of children for the current node. If there are no children (if the node is a leaf), this may return null or an array of length 0. Other code in this class will work correctly for both these cases. A caller may assume that either isLeaf() returns true, or this node has a nonzero number of children. So the following idiom is frequently useful:

    if ( ! tr.isLeaf()) {
        Tree[] kids = children();
        for (int i = 0; i < kids.length; i++) {
            doSomethingTo(kids[i]);
        }
    }
  

Returns:

The children of the node

See Also:

getChildrenAsList()

getChildrenAsList

public List getChildrenAsList()

Returns an array of children for the current node. If there are no children, then a (non-null) List of size 0 will be returned.

Returns:

The children of the node

setChildren

public abstract void setChildren(Tree[] children)

Set the children of this node to be the children given in the array. The children array may be either an array of length 0 or null if there are no children, and other methods in this class work on either representation.

Parameters:

children - The array of children, each a Tree

See Also:

setChildren(List)

setChildren

public void setChildren(List childTreesList)

Set the children of this tree node to the given list. This method is implemented in the Tree class by converting the List into a tree array and calling the array-based method. Subclasses which use a List-based representation of tree children should override this method. This implementation allows the case that the List is null: it yields a node with no children.

Parameters:

childTreesList - list of trees to become children

See Also:

setChildren(Tree[])

label

public Label label()

Returns the label associated with the current node, or null if there is no label. The default implementation always returns null.

Specified by:

label in interface Labeled

Returns:

The label of the node

setLabel

public void setLabel(Label label)

Sets the label associated with the current node, if there is one.

Specified by:

setLabel in interface Labeled

Parameters:

label - The label

score

public double score()

Returns the score associated with the current node, or NaN if there is no score. The default implementation returns NaN.

Specified by:

score in interface Scored

Returns:

The score

setScore

public void setScore(double score)

Sets the score associated with the current node, if there is one

Parameters:

score - The score

firstChild

public Tree firstChild()

Returns the first child of a tree, or null if none

Returns:

The first child

lastChild

public Tree lastChild()

Returns the last child of a tree, or null if none

Returns:

The last child

constituents

public Set constituents()

Returns the Constituents generated by the parse tree.

Returns:

a Set of the constituents as SimpleConstituent type

constituents

public Set constituents(ConstituentFactory cf)

Returns the Constituents generated by the parse tree.

toStringBuffer

public StringBuffer toStringBuffer(StringBuffer sb)

Appends the printed form of a parse tree (as a bracketed String) to a StringBuffer. The implementation of this may be more efficient than for toString() on complex trees.

Returns:

StringBuffer returns the StringBuffer

toString

public String toString()

Converts parse tree to string in Penn Treebank format. Get efficiency by chaining a single StringBuffer through it all.

Overrides:

toString in class AbstractCollection

Returns:

the tree as a bracketed list on one line

indentedListPrint

public void indentedListPrint()

Indented list printing of a tree. Includes tree node scores.

indentedListPrint

public void indentedListPrint(String indent,
                              String pad)

Indented list printing of a tree with each line indented

Parameters:

indent - The base String (normally just spaces) to print before each line of tree

pad - The additional String (normally just more spaces) to add when going to a deeper level of Tree. These are used rather than integer levels for efficiency.

pennPrint

public void pennPrint(PrintStream ps)

Print the tree as done in Penn Treebank merged files. The formatting should be exactly the same, but we don't print the trailing whitespace found in Penn Treebank trees. The basic deviation from a bracketed indented tree is to in general collapse the printing of adjacent preterminals onto one line of tags and words. Additional complexities are that conjunctions (tag CC) are not collapsed in this way, and that the unlabeled outer brackets are collapsed onto the same line as the next bracket down.

Parameters:

ps - The tree is printed to this PrintStream

pennPrint

public void pennPrint()

Print the tree as done in Penn Treebank merged files. The formatting should be exactly the same, but we don't print the trailing whitespace found in Penn Treebank trees. The tree is printed to System.out. The basic deviation from a bracketed indented tree is to in general collapse the printing of adjacent preterminals onto one line of tags and words. Additional complexities are that conjunctions (tag CC) are not collapsed in this way, and that the unlabeled outer brackets are collapsed onto the same line as the next bracket down.

depth

public int depth()

Finds the depth of the tree. The depth is defined as the length of the longest path from this node to a leaf node. Leaf nodes have depth zero.

Returns:

the depth

percolateHeads

public void percolateHeads(HeadFinder hf)

Finds the heads of the tree. This code assumes that the label does store and return sensible values for the category, word, and tag. It will be a no-op otherwise. The tree is modified. The routine assumes the Tree has word leaves and tag preterminals, and copies their category to word and tag respectively, if they have a null value.

Parameters:

hf - The headfinding algorithm to use

yield

public Sentence yield()

Gets the yield of the tree. The Label of all leaf nodes is returned as a list ordered by the natural left to right order of the leaves. Null values, if any, are inserted into the list like any other value.

Returns:

a List of the data in the tree's leaves.

yield

public List yield(List y)

Gets the yield of the tree. The Label of all leaf nodes is returned as a list ordered by the natural left to right order of the leaves. Null values, if any, are inserted into the list like any other value. This has been rewritten to thread, so only one List is used.

Parameters:

y - The list in which the yield of the tree will be placed. Normally, this will be empty when the routine is called, but if not, the new yield is added to the end of the list.

Returns:

a List of the data in the tree's leaves.

taggedYield

public Sentence taggedYield()

Gets the tagged yield of the tree. The Label of all leaf nodes is returned as a list ordered by the natural left to right order of the leaves. Null values, if any, are inserted into the list like any other value.

Returns:

a List of the data in the tree's leaves.

taggedYield

public List taggedYield(List ty)

Gets the tagged yield of the tree -- that is, get the preterminals as well as the terminals. The Label of all leaf nodes is returned as a list ordered by the natural left to right order of the leaves. Null values, if any, are inserted into the list like any other value. This has been rewritten to thread, so only one List is used.

Parameters:

ty - The list in which the tagged yield of the tree will be placed. Normally, this will be empty when the routine is called, but if not, the new yield is added to the end of the list.

Returns:

a List of the data in the tree's leaves.

preTerminalYield

public List preTerminalYield()

Gets the preterminal yield (i.e., tags) of the tree. All data in preleaf nodes is returned as a list ordered by the natural left to right order of the tree. Null values, if any, are inserted into the list like any other value. Pre-leaves are nodes of height 1.

Returns:

a List of the data in the tree's pre-leaves.

preTerminalYield

public List preTerminalYield(List y)

Gets the preterminal yield (i.e., tags) of the tree. All data in preleaf nodes is returned as a list ordered by the natural left to right order of the tree. Null values, if any, are inserted into the list like any other value. Pre-leaves are nodes of height 1.

Parameters:

y - The list in which the preterminals of the tree will be placed. Normally, this will be empty when the routine is called, but if not, the new yield is added to the end of the list.

Returns:

a List of the data in the tree's pre-leaves.

labels

public Collection labels()

Get the set of all node and leaf Labels, null or otherwise, contained in the tree.

Specified by:

labels in interface Labeled

Returns:

the Collection (actually, Set) of all values in the tree.

setLabels

public void setLabels(Collection c)

Description copied from interface: Labeled

Sets the labels associated with this object.

Specified by:

setLabels in interface Labeled

subTrees

public Set subTrees()

Get the set of all subtrees inside the tree by returning a tree rooted at each node. These are not copies, but all share structure.

Returns:

the Set of all subtrees in the tree.

subTrees

public Set subTrees(Set n)

Add the set of all subtrees inside a tree to the given Set.

Parameters:

n - A set of nodes to which the subtrees will be added

Returns:

The set parameter with the subtrees added

deepCopy

public Tree deepCopy()

Create a deep copy of the tree. The entire structure is recursively copied, but label data themselves are not cloned. The copy is built using a TreeFactory that will produce a Tree like the input one.

Returns:

a deep structural copy of the tree.

deepCopy

public Tree deepCopy(TreeFactory tf)

Create a deep copy of the tree. The entire structure is recursively copied, but label data themselves are not cloned. By specifying an appropriate TreeFactory, this method can be used to change the type of a Tree.

Parameters:

tf - The TreeFactory to be used for creating the returned Tree

Returns:

a deep structural copy of the tree.

transform

public Tree transform(TreeTransformer transformer)

Create a transformed Tree. The tree is traversed in a depth-first, left-to-right order, and the TreeTransformer is called on each node. It returns some Tree. The transformed tree has a new tree structure (i.e., a "deep copy" is done), but it will usually share its labels with the original tree.

Parameters:

transformer - The function that transforms tree nodes or subtrees

Returns:

a transformation of this Tree

transform

public Tree transform(TreeTransformer transformer,
                      TreeFactory tf)

Create a transformed Tree. The tree is traversed in a depth-first, left-to-right order, and the TreeTransformer is called on each node. It returns some Tree. The transformed tree has a new tree structure (i.e., a "deep copy" is done), but it will usually share its labels with the original tree.

Parameters:

transformer - The function that transforms tree nodes or subtrees

tf - The TreeFactory which will be used for creating new nodes for the returned Tree

Returns:

a transformation of this Tree

spliceOut

public Tree spliceOut(Filter nodeFilter)

Creates a (partial) deep copy of the tree, where all nodes that the filter does not accept are spliced out. If the result is not a tree (that is, it's a forest), an empty root node is generated.

Parameters:

nodeFilter - a Filter method which returns true to mean delete this node

Returns:

a filtered copy of the tree

spliceOut

public Tree spliceOut(Filter nodeFilter,
                      TreeFactory tf)

Creates a (partial) deep copy of the tree, where all nodes that the filter does not accept are spliced out. That is, the particular modes for which the Filter returns false are removed from the Tree, but those nodes' children are kept (assuming they pass the Filter, and they are added in the appropriate left-to-right ordering as new children of the parent node. If the root node is deleted, so that the result would not be a tree (that is, it's a forest), an empty root node is generated. If nothing is accepted, null is returned.

Parameters:

nodeFilter - a Filter method which returns true to mean delete this node

tf - A TreeFactory for making new trees. Used if the root node is deleted.

Returns:

a filtered copy of the tree.

prune

public Tree prune(Filter filter)

Creates a deep copy of the tree, where all nodes that the filter does not accept and all children of such nodes are pruned. If all ' of a node's children are pruned, that node is cut as well. A Filter can assume that it will not be called with a null argument.

Parameters:

filter - the filter to be apply

Returns:

a filtered copy of the tree.

prune

public Tree prune(Filter filter,
                  TreeFactory tf)

Creates a deep copy of the tree, where all nodes that the filter does not accept and all children of such nodes are pruned. If all ' of a node's children are pruned, that node is cut as well. A Filter can assume that it will not be called with a null argument.

Parameters:

filter - the filter to be apply

tf - the TreeFactory to be used to make new Tree nodes if needed

Returns:

a filtered copy of the tree.

treeFactory

public abstract TreeFactory treeFactory()

Return a TreeFactory that produces trees of the appropriate type.

Returns:

A factory to produce Trees

parent

public Tree parent()

Return the parent of the tree node. This routine may return null meaning simply that the implementation doesn't know how to determine the parent node, rather than there is no such node.

Returns:

the parent Tree node or null

See Also:

parent(Tree)

parent

public Tree parent(Tree root)

Return the parent of the tree node. This routine will traverse a tree (depth first) from the given root, and will correctly find the parent, regardless of whether the concrete class stores parents. It will only return null if this node is the root node, or if this node is not contained within the tree rooted at root.

Returns:

the parent Tree node if any; else null

size

public int size()

Returns the number of nodes the tree contains. This method implements the size() function required by the Collections interface. The size of the tree is the number of nodes it contains (of all types, including the leaf nodes and the root).

Specified by:

size in interface Collection

Specified by:

size in class AbstractCollection

Returns:

The size of the tree

See Also:

depth()

iterator

public Iterator iterator()

Returns an iterator over the nodes of the tree. This method implements the iterator() method required by the Collections interface. It does a preorder (children after node) traversal of the tree. (A possible extension to the class at some point would be to allow different traversal orderings via variant iterators.)

Specified by:

iterator in interface Collection

Specified by:

iterator in class AbstractCollection

Returns:

An interator over the nodes of the tree