edu.stanford.nlp.trees
Class Tree

java.lang.Object
  java.util.AbstractCollection
      edu.stanford.nlp.trees.Tree

All Implemented Interfaces:

Label, Labeled, Scored, Serializable, Iterable, Collection

Direct Known Subclasses:

LabeledScoredTreeLeaf, LabeledScoredTreeNode, SimpleTree, TreeGraphNode

public abstract class Tree
extends AbstractCollection
implements Label, Labeled, Scored, Serializable

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 two abstract methods that must be implemented are: children(), and treeFactory(). Note that setChildren(Tree[]) is now an optional operation, whereas it was previously was required to be implemented. 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.

Author:

Christopher Manning, Dan Klein

See Also:

Serialized Form

Field Summary

protected static Tree[]

ZEROCHILDREN A leaf node should have a zero-length array for its children.

Constructor Summary

Tree()

Method Summary

void	addChild(int i, Tree t) Adds the tree t at the index position among the daughters.
void	addChild(Tree t) Adds the tree t at the last index position among the daughters.
Tree	ancestor(int height, Tree root) Return the ancestor tree node height nodes up from the current node.
boolean	cCommands(Tree t1, Tree t2) Given nodes t1 and t2 which are dominated by this node, returns true iff t1 c-commands t2.
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.
Tree	deeperCopy() Same as deepCopy but makes a copy of the labels as well.
Tree	deeperCopy(TreeFactory tf) Same as deepCopy but will copy the labels over as well.
Set<Dependency>	dependencies() Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	dependencies(Filter f) Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	dependencies(Filter f, HeadFinder hf) Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	dependencies(HeadFinder hf) Return a set of Word-Word dependencies, represented as Dependency objects for the Tree.
int	depth() Finds the depth of the tree.
boolean	dominates(Tree t) returns true if this dominates the Tree passed in as an argument.
List<Tree>	dominationPath(Tree t) returns the path of nodes leading down to a dominated node, including this and the dominated node itself.
boolean	equals(Object o) Implements equality for Tree's.
Tree	firstChild() Returns the first child of a tree, or null if none.
Tree	flatten() Return a flattened version of a tree.
Tree	flatten(TreeFactory tf) Return a flattened version of a tree.
Tree	getChild(int i) Return the child at some daughter index.
List<Tree>	getChildrenAsList() Returns an array of children for the current node.
List<Tree>	getLeaves() Gets the leaves of the tree.
List<Tree>	getLeaves(List<Tree> list) Gets the leaves of the tree.
IntPair	getSpan()
int	hashCode() Implements a hashCode for Tree's.
Tree	headPreTerminal(HeadFinder hf) Returns the preterminal tree that is the head of the tree.
Tree	headTerminal(HeadFinder hf) Returns the tree leaf that is the head of the tree.
void	indentedListPrint() Indented list printing of a tree.
void	indentedListPrint(PrintWriter pw, boolean printScores) Indented list printing of a tree.
int	indexOf(Tree tree) Returns the position of a Tree in the children list, if present, or -1 if it is not present.
void	insertDtr(Tree dtr, int position) insert dtr after position existing daughters in this.
boolean	isLeaf() Says whether a node is a leaf.
boolean	isPhrasal() Return whether this node is a phrasal node or not.
boolean	isPrePreTerminal() Return whether all the children of this node are preterminals or not.
boolean	isPreTerminal() Return whether this node is a preterminal or not.
boolean	isUnaryRewrite() Says whether the current node has only one child.
Iterator	iterator() Returns an iterator over the nodes of the tree.
Tree	joinNode(Tree t1, Tree t2) Given nodes t1 and t2 which are dominated by this node, returns their "join node": the node j such that j dominates both t1 and t2, and no other node which also dominates both t1 and t2 dominates j.
Label	label() Returns the label associated with the current node, or null if there is no label.
LabelFactory	labelFactory() Returns a factory that makes labels of the same type as this one.
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.
int	leftCharEdge(Tree node) Returns the positional index of the left edge of node within the tree, as measured by characters.
Tree	localTree() Returns a new Tree that represents the local Tree at a certain node.
String	nodeString()
int	numChildren() Says how many children a tree node has in its local tree.
Tree	parent() Return the parent of the tree node.
Tree	parent(Tree root) Return the parent of the tree node.
List	pathNodeToNode(Tree t1, Tree t2) Given nodes t1 and t2 which are dominated by this node, returns a list of all the nodes on the path from t1 to t2, inclusive, or null if none found.
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	pennPrint(PrintWriter pw) Print the tree as done in Penn Treebank merged files.
String	pennString() Calls pennPrint() and saves output to a String
void	percolateHeads(HeadFinder hf) Finds the heads of the tree.
List<Label>	preTerminalYield() Gets the preterminal yield (i.e., tags) of the tree.
List<Label>	preTerminalYield(List<Label> y) Gets the preterminal yield (i.e., tags) of the tree.
void	printLocalTree()
void	printLocalTree(PrintWriter pw)
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.
Tree	removeChild(int i) Destructively removes the child at some daughter index and returns it.
int	rightCharEdge(Tree node) Returns the positional index of the right edge of node within the tree, as measured by characters.
double	score() Returns the score associated with the current node, or NaN if there is no score.
Tree	setChild(int i, Tree t) Replaces the ith child of this with the tree t.
void	setChildren(List childTreesList) Set the children of this tree node to the given list.
void	setChildren(Tree[] children) Set the children of this node to be the children given in the array.
void	setFromString(String labelStr) Set the contents of this label to this String representing the complete contents of the label.
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.
void	setSpans()
void	setValue(String value) Set the value for the label (if one is stored).
List<Tree>	siblings(Tree root) Returns the siblings of this Tree node.
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.
List<Tree>	subTreeList() Get the list of all subtrees inside the tree by returning a tree rooted at each node.
Set<Tree>	subTrees() Get the set of all subtrees inside the tree by returning a tree rooted at each node.
Collection<Tree>	subTrees(Collection<Tree> n) Add the set of all subtrees inside a tree (including the tree itself) to the given Collection.
Set<Dependency>	taggedDependencies() Return a Set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	taggedDependencies(Filter f) Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	taggedDependencies(Filter f, HeadFinder hf) Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree.
Set<Dependency>	taggedDependencies(HeadFinder hf) Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects for the Tree.
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.
List<TypedDependency>	typedDependencies() Return a list of English typed dependencies, as identified and labelled by the GrammaticalRelation class.
List<TypedDependency>	typedDependenciesCollapsed() Return a list of English collapsed typed dependencies, as identified and labelled by the GrammaticalRelation class.
List<TypedDependency>	typedDependenciesCollapsed(Filter<TypedDependency> f) Return a list of English collapsed typed dependencies, as identified and labelled by the GrammaticalRelation class.
Tree	upperMostUnary(Tree root) In case this node is the only child of its parent, trace up the chain of unaries, and return the uppermost node of the chain (the node whose parent has multiple children, or the node that is the root of the tree
String	value() Return a String representation of just the "main" value of this label.
static Tree	valueOf(String str) This gives you a tree from a String representation (as a bracketed Tree, of the kind produced by toString(), pennPrint(), or as in the Penn Treebank).
static Tree	valueOf(String str, TreeReaderFactory trf) This gives you a tree from a String representation (as a bracketed Tree, of the kind produced by toString(), pennPrint(), or as in the Penn Treebank.
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, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

ZEROCHILDREN

protected static final Tree[] ZEROCHILDREN

A leaf node should have a zero-length array for its children. For efficiency, subclasses can use this array as a return value for children() for leaf nodes if desired. Should this be public instead?

Constructor Detail

Tree

public Tree()

Method Detail

isLeaf

public boolean isLeaf()

Says whether a node is a leaf. Can be used on an arbitrary Tree. Being a leaf is defined as having no children. This must be implemented as returning a zero-length Tree[] array for children(). This is the preferred alternative to running meta checks on types, as it works independent of Tree implementation.

Returns:

true if this object is a leaf

numChildren

public int numChildren()

Says how many children a tree node has in its local tree. Can be used on an arbitrary Tree. Being a leaf is defined as having no children.

Returns:

The number of direct children of the tree node

isUnaryRewrite

public boolean isUnaryRewrite()

Says whether the current node has only one child. Can be used on an arbitrary Tree.

Returns:

Whether the node heads a unary rewrite

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

isPrePreTerminal

public boolean isPrePreTerminal()

Return whether all the children of this node are preterminals or not. A preterminal is defined to be a node with one child which is itself a leaf. Considered false if the node has no children

Returns:

true if the node is a prepreterminal; false otherwise

isPhrasal

public boolean isPhrasal()

Return whether this node is a phrasal node or not. A phrasal node is defined to be a node which is not a leaf or a preterminal. Worded positively, this means that it must have two or more children, or one child that is not a leaf.

Returns:

true if the node is phrasal; false otherwise

equals

public boolean equals(Object o)

Implements equality for Tree's. Two Tree objects are equal if they have equal Labels, the same number of children, and their children are pairwise equal.

Specified by:

equals in interface Collection

Overrides:

equals in class Object

Parameters:

o - The object to compare with

Returns:

Whether two things are equal

hashCode

public int hashCode()

Implements a hashCode for Tree's. Two trees should have the same hashcode if they are equal, so we hash on the label, the label and the children's labels.

Specified by:

hashCode in interface Collection

Overrides:

hashCode in class Object

Returns:

The hash code

indexOf

public int indexOf(Tree tree)

Returns the position of a Tree in the children list, if present, or -1 if it is not present. Trees are checked for presence with equals().

Parameters:

tree - The tree to look for in children list

Returns:

Its index in the list or -1

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 must return a Tree[] array of length 0. A null children() value for tree leaves was previously supported, but no longer is. A caller may assume that either isLeaf() returns true, or this node has a nonzero number of children.

Returns:

The children of the node

See Also:

getChildrenAsList()

getChildrenAsList

public List<Tree> 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 void setChildren(Tree[] children)

Set the children of this node to be the children given in the array. This is an optional operation; by default it is unsupported. Note for subclasses that if there are no children, the children() method must return a Tree[] array of length 0. This class gives subclasses access to a protected ZEROCHILDREN canonical zero-length Tree[] array to represent zero children, but it is not required that leaf nodes use this particular zero-length array to represent a leaf node.

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 (represented by a canonical zero-length children() array).

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

upperMostUnary

public Tree upperMostUnary(Tree root)

In case this node is the only child of its parent, trace up the chain of unaries, and return the uppermost node of the chain (the node whose parent has multiple children, or the node that is the root of the tree

Parameters:

root - The root of the tree that contains this subtree

Returns:

The uppermost node of the unary chain, if this node is in a unary chain, or else the current node

setSpans

public void setSpans()

getSpan

public IntPair getSpan()

constituents

public Set constituents()

Returns the Constituents generated by the parse tree.

Returns:

a Set of the constituents as constituents of type SimpleConstituent

constituents

public Set constituents(ConstituentFactory cf)

Returns the Constituents generated by the parse tree. The Constituents of a sentence include the preterminal categories but not the leaves.

Parameters:

cf - ConstituentFactory used to build the Constituent objects

Returns:

a Set of the constituents as SimpleConstituent type (in the current implementation, a HashSet

localTree

public Tree localTree()

Returns a new Tree that represents the local Tree at a certain node. That is, it builds a new tree that copies the mother and daughter nodes (but not their Labels), as non-Leaf nodes, but zeroes out their children.

Returns:

A local 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.

Parameters:

sb - The StringBuffer to append to

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.

Specified by:

toString in interface Label

Overrides:

toString in class AbstractCollection

Returns:

the tree as a bracketed list on one line

printLocalTree

public void printLocalTree()

printLocalTree

public void printLocalTree(PrintWriter pw)

indentedListPrint

public void indentedListPrint()

Indented list printing of a tree. The tree is printed in an indented list notation, with nodel labels followed by node scores.

indentedListPrint

public void indentedListPrint(PrintWriter pw,
                              boolean printScores)

Indented list printing of a tree. The tree is printed in an indented list notation, with nodel labels followed by node scores.

Parameters:

pw - The PrintWriter to print the tree to

nodeString

public String nodeString()

pennPrint

public void pennPrint(PrintWriter pw)

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:

pw - The tree is printed to this PrintWriter

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

pennString

public String pennString()

Calls pennPrint() and saves output to a String

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

headTerminal

public Tree headTerminal(HeadFinder hf)

Returns the tree leaf that is the head of the tree.

Parameters:

hf - The headfinding algorithm to use

Returns:

The head tree leaf if any, else null

headPreTerminal

public Tree headPreTerminal(HeadFinder hf)

Returns the preterminal tree that is the head of the tree. See isPreTerminal() for the definition of a preterminal node. Beware that some tree nodes may have no preterminal head.

Parameters:

hf - The headfinding algorithm to use

Returns:

The head preterminal tree, if any, else null

Throws:

IllegalArgumentException - if called on a leaf node

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

dependencies

public Set<Dependency> dependencies()

Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree. This will only give useful results if the internal tree node labels support HasWord and head percolation has already been done (see percolateHeads()).

Returns:

Set of dependencies (each a Dependency)

dependencies

public Set<Dependency> dependencies(Filter f)

Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree. This will only give useful results if the internal tree node labels support HasWord and head percolation has already been done (see percolateHeads()).

Parameters:

f - Dependencies are excluded for which the Dependency is not accepted by the Filter

Returns:

Set of dependencies (each a Dependency)

dependencies

public Set<Dependency> dependencies(HeadFinder hf)

Return a set of Word-Word dependencies, represented as Dependency objects for the Tree.

Parameters:

hf - The HeadFinder to use to identify the head of constituents

Returns:

Set of dependencies (each a Dependency)

dependencies

public Set<Dependency> dependencies(Filter f,
                                    HeadFinder hf)

Return a set of Word-Word dependencies, represented as Dependency objects, for the Tree.

Parameters:

f - Dependencies are excluded for which the Dependency is not accepted by the Filter

hf - The HeadFinder to use to identify the head of constituents. If this is null, then nodes are assumed to already be marked with their heads.

Returns:

Set of dependencies (each a Dependency)

taggedDependencies

public Set<Dependency> taggedDependencies()

Return a Set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree. This will only give useful results if the internal tree node labels support HasWord and HasTag, and head percolation has already been done (see percolateHeads()).

Returns:

Set of dependencies (each a Dependency)

taggedDependencies

public Set<Dependency> taggedDependencies(Filter f)

Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree. This will only give useful results if the internal tree node labels support HasWord and head percolation has already been done (see percolateHeads()).

Implementation note: It would be nice to generalize this with dependencies() to use a LabelFactory, but it seems impossible with the current setup.

Parameters:

f - Dependencies are excluded for which the Dependency is not accepted by the Filter

Returns:

Set of dependencies (each a Dependency)

taggedDependencies

public Set<Dependency> taggedDependencies(HeadFinder hf)

Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects for the Tree.

Parameters:

hf - The HeadFinder to use to identify the head of constituents

Returns:

Set of dependencies (each a Dependency)

taggedDependencies

public Set<Dependency> taggedDependencies(Filter f,
                                          HeadFinder hf)

Return a set of TaggedWord-TaggedWord dependencies, represented as Dependency objects, for the Tree.

Parameters:

f - Dependencies are excluded for which the Dependency is not accepted by the Filter

hf - The HeadFinder to use to identify the head of constituents. If this is null, then nodes are assumed to already be marked with their heads.

Returns:

Set of dependencies (each a Dependency)

typedDependencies

public List<TypedDependency> typedDependencies()

Return a list of English typed dependencies, as identified and labelled by the GrammaticalRelation class.

Returns:

The TypedDependencies for the tree

typedDependenciesCollapsed

public List<TypedDependency> typedDependenciesCollapsed()

Return a list of English collapsed typed dependencies, as identified and labelled by the GrammaticalRelation class. These dependencies assume the tree is in English.

typedDependenciesCollapsed

public List<TypedDependency> typedDependenciesCollapsed(Filter<TypedDependency> f)

Return a list of English collapsed typed dependencies, as identified and labelled by the GrammaticalRelation class. These dependencies assume the tree is in English.

Parameters:

f - A filter to exclude certain dependencies

Returns:

The collapsed typed dependencies for the tree

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<Label> 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<Label> preTerminalYield(List<Label> 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.

getLeaves

public List<Tree> getLeaves()

Gets the leaves of the tree. All leaves nodes are 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.

Returns:

a List of the leaves.

getLeaves

public List<Tree> getLeaves(List<Tree> list)

Gets the leaves of the tree.

Parameters:

list - The list in which the leaves 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 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

Parameters:

c - The set of Label values

flatten

public Tree flatten()

Return a flattened version of a tree. In many circumstances, this will just return the tree, but if the tree is something like a binarized version of a dependency grammar tree, then it will be flattened back to a dependency grammar tree representation. Formally, a node will be removed from the tree when: it is not a terminal or preterminal, and its label()equal() to the label() of its parent, and all its children will then be promoted to become children of the parent (in the same position in the sequence of daughters.

Returns:

A flattened version of this tree.

flatten

public Tree flatten(TreeFactory tf)

Return a flattened version of a tree. In many circumstances, this will just return the tree, but if the tree is something like a binarized version of a dependency grammar tree, then it will be flattened back to a dependency grammar tree representation. Formally, a node will be removed from the tree when: it is not a terminal or preterminal, and its label()equal() to the label() of its parent, and all its children will then be promoted to become children of the parent (in the same position in the sequence of daughters.

Note: In the current implementation, the tree structure is mainly duplicated, but the links between preterminals and terminals aren't.

Parameters:

tf - TreeFactory used to create tree structure for flattened tree

Returns:

A flattened version of this tree.

subTrees

public Set<Tree> 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. The tree is regarded as a subtree of itself.

Returns:

the Set of all subtrees in the tree.

subTreeList

public List<Tree> subTreeList()

Get the list of all subtrees inside the tree by returning a tree rooted at each node. These are not copies, but all share structure. The tree is regarded as a subtree of itself.

Returns:

the List of all subtrees in the tree.

subTrees

public Collection<Tree> subTrees(Collection<Tree> n)

Add the set of all subtrees inside a tree (including the tree itself) to the given Collection.

Parameters:

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

Returns:

The collection parameter with the subtrees added

deeperCopy

public Tree deeperCopy()

Same as deepCopy but makes a copy of the labels as well. Uses the TreeFactory of the root node given by treeFactory(). Assumes that your labels give a non-null labelFactory(). (Added by Aria Haghighi.)

Returns:

A deep copy of the tree structure and its labels

deeperCopy

public Tree deeperCopy(TreeFactory tf)

Same as deepCopy but will copy the labels over as well. Each Label is copied using the labelFactory() returned by the corresponding node's label. It assumes that your labels give non-null labelFactory. (Added by Aria Haghighi.) *

Parameters:

tf - The TreeFactory used to make all nodes in the copied tree structure

Returns:

A Tree that is a deep copy of the tree structure and Labels of the original tree.

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 keep this node, false to mean delete it

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 keep this node, false to mean delete it

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.

For example, the following code excises all PP nodes from a Tree: Filter f = new Filter { public boolean accept(Tree t) { return ! t.label().value().equals("PP"); } } tree.prune(f);

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, including the possibility of null if the root node of the tree is filtered

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.

Parameters:

root - The root node of the whole Tree

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()

ancestor

public Tree ancestor(int height,
                     Tree root)

Return the ancestor tree node height nodes up from the current node.

Parameters:

height - How many nodes up to go. A parameter of 0 means return this node, 1 means to return the parent node and so on.

Returns:

The ancestor at height height. It returns null if it does not exist or the tree implementation does not keep track of parents

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 Iterable

Specified by:

iterator in interface Collection

Specified by:

iterator in class AbstractCollection

Returns:

An interator over the nodes of the tree

valueOf

public static Tree valueOf(String str)
                    throws IOException

This gives you a tree from a String representation (as a bracketed Tree, of the kind produced by toString(), pennPrint(), or as in the Penn Treebank). It's not the most efficient thing to do for heavy duty usage. The Tree returned is created by a StringLabeledScoredTreeReaderFactory.

Parameters:

str - The tree as a bracketed list in a String.

Returns:

The Tree

Throws:

IOException - If Tree format is not valid

valueOf

public static Tree valueOf(String str,
                           TreeReaderFactory trf)
                    throws IOException

This gives you a tree from a String representation (as a bracketed Tree, of the kind produced by toString(), pennPrint(), or as in the Penn Treebank. It's not the most efficient thing to do for heavy duty usage.

Parameters:

str - The tree as a bracketed list in a String.

Returns:

The Tree

Throws:

IOException - If Tree format is not valid

getChild

public Tree getChild(int i)

Return the child at some daughter index.

Parameters:

i - The daughter index

Returns:

The tree at that daughter index

removeChild

public Tree removeChild(int i)

Destructively removes the child at some daughter index and returns it. Note that this method will throw an ArrayIndexOutOfBoundsException if the daughter index is too big for the list of daughters.

Parameters:

i - The daughter index

Returns:

The tree at that daughter index

addChild

public void addChild(int i,
                     Tree t)

Adds the tree t at the index position among the daughters. Note that this method will throw an ArrayIndexOutOfBoundsException if the the daughter index is too big for the list of daughters.

Parameters:

i - the index position at which to add the new daughter

t - the new daughter

addChild

public void addChild(Tree t)

Adds the tree t at the last index position among the daughters.

Parameters:

t - the new daughter

setChild

public Tree setChild(int i,
                     Tree t)

Replaces the ith child of this with the tree t. Note that this method will throw an ArrayIndexOutOfBoundsException if the the child index is too big for the list of children.

Parameters:

i - The index position at which to replace the child

t - The new child

Returns:

The tree that was previously the ith d

dominates

public boolean dominates(Tree t)

returns true if this dominates the Tree passed in as an argument.

dominationPath

public List<Tree> dominationPath(Tree t)

returns the path of nodes leading down to a dominated node, including this and the dominated node itself. Returns null if t is not dominated by this. Object equality (==) is the relevant criterion.

pathNodeToNode

public List pathNodeToNode(Tree t1,
                           Tree t2)

Given nodes t1 and t2 which are dominated by this node, returns a list of all the nodes on the path from t1 to t2, inclusive, or null if none found.

joinNode

public Tree joinNode(Tree t1,
                     Tree t2)

Given nodes t1 and t2 which are dominated by this node, returns their "join node": the node j such that j dominates both t1 and t2, and no other node which also dominates both t1 and t2 dominates j. (Remember that domination is defined such that every node dominates itself.) Returns null if no such node can be found.

cCommands

public boolean cCommands(Tree t1,
                         Tree t2)

Given nodes t1 and t2 which are dominated by this node, returns true iff t1 c-commands t2. (A node c-commands its sister(s) and any nodes below its sister(s).)

siblings

public List<Tree> siblings(Tree root)

Returns the siblings of this Tree node.

Parameters:

root - The root within which this tree node is contained

Returns:

The siblings as a list, an empty list if there are no siblings

insertDtr

public void insertDtr(Tree dtr,
                      int position)

insert dtr after position existing daughters in this.

value

public String value()

Description copied from interface: Label

Return a String representation of just the "main" value of this label.

Specified by:

value in interface Label

Returns:

the "value" of the label

setValue

public void setValue(String value)

Description copied from interface: Label

Set the value for the label (if one is stored).

Specified by:

setValue in interface Label

Parameters:

value - - the value for the label

setFromString

public void setFromString(String labelStr)

Description copied from interface: Label

Set the contents of this label to this String representing the complete contents of the label. A class implementing label may throw an UnsupportedOperationException for this method (only). Typically, this method would do some appropriate decoding of the string in a way that sets multiple fields in an inverse of the toString() method.

Specified by:

setFromString in interface Label

Parameters:

labelStr - the String that translates into the content of the label

labelFactory

public LabelFactory labelFactory()

Returns a factory that makes labels of the same type as this one. May return null if no appropriate factory is known.

Specified by:

labelFactory in interface Label

Returns:

the LabelFactory for this kind of label

leftCharEdge

public int leftCharEdge(Tree node)

Returns the positional index of the left edge of node within the tree, as measured by characters. Returns -1 if node is not found.

rightCharEdge

public int rightCharEdge(Tree node)

Returns the positional index of the right edge of node within the tree, as measured by characters. Returns -1 if node is not found.