net.junaraki.libtree

Class AbstractTree<E>

java.lang.Object

java.util.AbstractCollection<E>

net.junaraki.libtree.AbstractTree<E>

Type Parameters:

E - the type of elements in this tree

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>, Tree<E>

Direct Known Subclasses:

OrderedTree, UnorderedTree

public abstract class AbstractTree<E>
extends java.util.AbstractCollection<E>
implements Tree<E>

This class provides a skeletal implementation of the tree interface. Without making a sharp distinction between an entire tree and an individual node, the class supports various methods to work on an entire tree or on a particular node. In order to make this class as general as possible, it only provides methods that return a value of a primitive type such as int or boolean, not instances of the Type type. Note that child nodes may have duplicate elements.

Author:

Jun Araki

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	PAREN_END
static java.lang.String	PAREN_START

Constructor Summary

Constructors

Constructor and Description
AbstractTree() Public constructor.
AbstractTree(E element) Public constructor.

Method Summary

Modifier and Type	Method and Description
boolean	add(E e) Adds a child with the given element.
int	degree() Returns the degree of this tree.
int	degree(Tree<E> node) Returns the degree of the given node.
int	depth() Returns the depth of this tree.
int	depth(Tree<E> node) Returns the depth of the given node.
E	getElement() Returns the element of this node.
java.util.List<E>	getLeafElements() Returns a list of leaf elements in this tree in a natural order.
boolean	hasAncestor(E element) Returns true if this node has an ancestor with the given element.
boolean	hasAncestor(Tree<E> ancestor) Returns true if this node has the given ancestor.
boolean	hasChild() Returns true if this node has a child.
boolean	hasDescendant(E element) Returns true if this node has a descendant with the given element.
boolean	hasDescendant(Tree<E> descendant) Returns true if this node has the given descendant.
boolean	hasElement() Returns true if this node has an element.
boolean	hasElement(E element) Returns true if this node has the given element.
boolean	hasParent() Returns true if this node has a parent.
boolean	hasParent(E element) Returns true if this node has a parent with the given element.
boolean	hasParent(Tree<E> parent) Returns true if this node has the given parent.
boolean	isBalanced() Returns true if this tree is balanced.
boolean	isLabeled() Returns true if this node is labeled.
boolean	isLabeledTree(java.util.Set<E> alphabet) Returns true if this tree is a labeled tree.
boolean	isLeaf() Returns true if this node is a leaf.
boolean	isRoot() Returns true if this node is the root.
java.util.Iterator<E>	iterator() Returns the iterator of this tree.
int	numLeaves() Returns the number of leaves of this tree.
void	removeChildren(java.util.Collection<E> elements) Removes children with one of the given elements from this node.
void	setElement(E element) Sets the given element to this node.
int	size() Returns the number of nodes in this tree.
java.util.List<E>	yield() Returns the yield of this tree as a list of elements of leaves.

Methods inherited from class java.util.AbstractCollection

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

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.junaraki.libtree.Tree

addChild, equals, find, findChild, getAncestorElements, getElements, getNodes, getParent, getRoot, getSiblingElements, hasChild, hashCode, numChildren, numSiblings, remove, removeChild, removeChildren

Methods inherited from interface java.util.Collection

addAll, clear, contains, containsAll, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

PAREN_START

public static final java.lang.String PAREN_START

See Also:

Constant Field Values

PAREN_END

public static final java.lang.String PAREN_END

See Also:

Constant Field Values

Constructor Detail

AbstractTree

public AbstractTree()

Public constructor.

AbstractTree

public AbstractTree(E element)

Public constructor.

Parameters:

element - an element of this node

Method Detail

iterator

public java.util.Iterator<E> iterator()

Returns the iterator of this tree.

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

Returns:

the iterator of this tree

size

public int size()

Returns the number of nodes in this tree.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in class java.util.AbstractCollection<E>

Returns:

the number of nodes in this tree

depth

public int depth()

Returns the depth of this tree. The depth of a tree is defined as the maximum depth of a node in the tree.

Specified by:

depth in interface Tree<E>

Returns:

the depth of this tree

depth

public int depth(Tree<E> node)

Returns the depth of the given node. The depth of a node is defined as the number edges on the path from the node to this node (as a root node). Returns -1 if this node is not an ancestor of the given node.

Specified by:

depth in interface Tree<E>

Parameters:

node - a node whose depth will be returned

Returns:

the depth of the given node

hasParent

public boolean hasParent()

Returns true if this node has a parent.

Specified by:

hasParent in interface Tree<E>

Returns:

true if this node has a parent; false otherwise

hasParent

public boolean hasParent(E element)

Returns true if this node has a parent with the given element.

Specified by:

hasParent in interface Tree<E>

Parameters:

element - an element whose presence in the parent of this node will be tested

Returns:

true if this node has a parent with the given element; false otherwise

hasParent

public boolean hasParent(Tree<E> parent)

Returns true if this node has the given parent.

Specified by:

hasParent in interface Tree<E>

Parameters:

parent - a parent whose presence in this node will be tested

Returns:

true if this node has the given parent; false otherwise

isRoot

public boolean isRoot()

Returns true if this node is the root.

Specified by:

isRoot in interface Tree<E>

Returns:

true if this node is the root; false otherwise

degree

public int degree()

Returns the degree of this tree. The degree of a tree is defined as the maximum degree of a node in the tree.

Specified by:

degree in interface Tree<E>

Returns:

the degree of this tree

degree

public int degree(Tree<E> node)

Returns the degree of the given node. The degree of a node is defined as the number of children of the node.

Specified by:

degree in interface Tree<E>

Parameters:

node - a node whose degree will be returned

Returns:

the degree of the given node

hasChild

public boolean hasChild()

Returns true if this node has a child.

Specified by:

hasChild in interface Tree<E>

Returns:

true if this node has a child; false otherwise

add

public boolean add(E e)

Adds a child with the given element.

Specified by:

add in interface java.util.Collection<E>

Overrides:

add in class java.util.AbstractCollection<E>

Parameters:

e - an element that will be added to the children of this node

Returns:

true if this collection changed as a result of the call

removeChildren

public void removeChildren(java.util.Collection<E> elements)

Removes children with one of the given elements from this node. This operation removes the children and their all descendants.

Specified by:

removeChildren in interface Tree<E>

Parameters:

elements - a collection of elements to be removed from the children of this node

hasAncestor

public boolean hasAncestor(E element)

Returns true if this node has an ancestor with the given element.

Specified by:

hasAncestor in interface Tree<E>

Parameters:

element - an element whose presence in the ancestors of this node will be tested

Returns:

true if this node has the given ancestor; false otherwise

hasAncestor

public boolean hasAncestor(Tree<E> ancestor)

Returns true if this node has the given ancestor.

Specified by:

hasAncestor in interface Tree<E>

Parameters:

ancestor - an ancestor whose presence for this node will be tested

Returns:

true if this node has the given ancestor; false otherwise

hasDescendant

public boolean hasDescendant(E element)

Returns true if this node has a descendant with the given element.

Specified by:

hasDescendant in interface Tree<E>

Parameters:

element - an element whose presence in the descendants of this node will be tested

Returns:

true if this node has the given descendant; false otherwise

hasDescendant

public boolean hasDescendant(Tree<E> descendant)

Returns true if this node has the given descendant.

Specified by:

hasDescendant in interface Tree<E>

Parameters:

descendant - a descendant whose presence for this node will be tested

Returns:

true if this node has the given descendant; false otherwise

isLeaf

public boolean isLeaf()

Returns true if this node is a leaf.

Specified by:

isLeaf in interface Tree<E>

Returns:

true if this node is a leaf; false otherwise

numLeaves

public int numLeaves()

Returns the number of leaves of this tree.

Specified by:

numLeaves in interface Tree<E>

Returns:

the number of leaves of this tree

getElement

public E getElement()

Returns the element of this node.

Specified by:

getElement in interface Tree<E>

Returns:

the element of this node

setElement

public void setElement(E element)

Sets the given element to this node.

Specified by:

setElement in interface Tree<E>

Parameters:

element - an element that will be set to this node

hasElement

public boolean hasElement()

Returns true if this node has an element.

Specified by:

hasElement in interface Tree<E>

Returns:

true if this node has an element; false otherwise

hasElement

public boolean hasElement(E element)

Returns true if this node has the given element.

Specified by:

hasElement in interface Tree<E>

Parameters:

element - an element whose presence in this node will be tested

Returns:

true if this node has the given element; false otherwise

isLabeled

public boolean isLabeled()

Returns true if this node is labeled.

Specified by:

isLabeled in interface Tree<E>

Returns:

true if this node is labeled; false otherwise

isLabeledTree

public boolean isLabeledTree(java.util.Set<E> alphabet)

Returns true if this tree is a labeled tree. A labeled tree is defined as a tree such that each node has a symbol assigned from a fixed finite alphabet.

Specified by:

isLabeledTree in interface Tree<E>

Parameters:

alphabet - a set of elements to be compared with elements in this tree

Returns:

true if this tree is a labeled tree; false otherwise

yield

public java.util.List<E> yield()

Returns the yield of this tree as a list of elements of leaves.

Specified by:

yield in interface Tree<E>

Returns:

the yield of this tree

getLeafElements

public java.util.List<E> getLeafElements()

Returns a list of leaf elements in this tree in a natural order.

Returns:

a list of leaf elements in this tree

isBalanced

public boolean isBalanced()

Returns true if this tree is balanced. A balanced tree is a tree such that all leaves of the tree are at the same depth.

Specified by:

isBalanced in interface Tree<E>

Returns:

true if this tree is balanced; false otherwise