All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class graph.Tree

java.lang.Object
   |
   +----graph.Tree

public abstract class Tree
extends Object
implements Cloneable
This class supports processing of recursive types that can be classified as trees. Recursive types are classes containing members of the same type. Data of recursive types are usually viewed as directed graphs. Recursive references represent directed edges. Each object of a recursive class represents a node in a graph as well as a subgraph rooted at this node. Trees constitute a subset of graphs. In a tree, a unique edge leads to each node. Each object of class Tree also can be viewed as a representation of the subtree whose top node is this object. Every node holds references to children. This class provides access to the parent of each node. Access to immediate children of each node is indexed. Tree is an abstract class. Methods nodeEqual and nodeCopy are abstract and should be defined in a derived class. Class Tree contains methods that implement various tree modifications. It also has methods implementing tree comparison and pattern matching. Terminal nodes called slots are utilized as place holders matched against trees. This class is useful for processing symbolic expressions.


Constructor Index

 o Tree()

Method Index

 o clean()
Cuts off the first children of all trees associated with slots in this Tree.
 o clone()
Clones this tree.
 o congruent(Tree)
Compares the specified Tree with this.
 o contains(Tree)
Checks if the specified Tree is a subtree of this.
 o cutoff()
Cuts off all children from this.
 o depth()
Returns the number of edges between this node and the root.
 o embed(Tree, int)
Embeds the specified Tree as a child of this tree.
 o embedCopy(Tree, int)
Clones the specified Tree and embeds it as a child of this tree.
 o firstIndex()
Returns the index of the first non-null child or -1 if there are no children.
 o getParent()
Returns the parent of this node.
 o getReference(int)
Yields the child with the specified index.
 o getRoot()
Returns the root.
 o getSlotValue()
Yields the value stored as the first child of the tree associated with this slot.
 o insertNodeCopy(Tree, int)
Duplicates the tip node of the specified Tree and inserts it between this and its parent.
 o instantiate()
Instantiates this Tree that is presumably a pattern.
 o isLeaf()
Checks if this node has no children.
 o isRoot()
Checks if this node is a tree root.
 o isSlot()
Returns true if this is a slot.
 o iterator()
Creates an instance of TreeIterator for use in iteration over the nodes of the tree rooted at this.
 o lastIndex()
Returns the index of the last non-null child) or -1 if there are no children.
 o match(Tree)
Checks if this and the specified Tree match.
 o maxIndex()
Yields the maximum possible child index.
 o nextIndex(int)
Returns the index of the next non-null child.
 o nodeCopy()
Clones a node without children
 o nodeEqual(Tree)
Returns a boolean value indicating if this node is equal to the specified node.
 o parentIndex()
Returns the index of this as a child of its parent.
 o relates(Tree)
Checks if this and the the specified Tree have the same root.
 o setReference(int, Tree)
Replaces the child with the specified index with the specified Tree.
 o setSlotValue(Tree)
Stores the specified tree as the first child of the tree associated with this slot.
 o slot(Tree)
Turns this, which is presumably a leaf node, into a slot and associates the specified Tree with the slot.
 o substitute(Tree)
Substitutes the specified Tree for this.
 o substituteCopy(Tree)
Clones and substitutes the specified Tree for this.

Constructors

 o Tree
 public Tree()

Methods

 o slot
 public synchronized void slot(Tree t)
Turns this, which is presumably a leaf node, into a slot and associates the specified Tree with the slot. The associated Tree is a place holder for match method. The tree associated with this should be root and leaf. Its first child of the associated Tree will be used for storing trees by method match. This retains its leaf node status.

Parameters:
t - associated tree
 o isSlot
 public boolean isSlot()
Returns true if this is a slot. Otherwise, false is returned.

 o getReference
 protected Tree getReference(int n)
Yields the child with the specified index.

Parameters:
n - child index
 o setReference
 protected synchronized void setReference(int n,
                                          Tree g)
Replaces the child with the specified index with the specified Tree.

Parameters:
n - index of the child to replace
g - tree that replaces a child
 o getSlotValue
 public Tree getSlotValue()
Yields the value stored as the first child of the tree associated with this slot.

 o setSlotValue
 public synchronized void setSlotValue(Tree g)
Stores the specified tree as the first child of the tree associated with this slot.

Parameters:
g - tree that is assigned to this slot
 o maxIndex
 protected int maxIndex()
Yields the maximum possible child index.

 o nodeEqual
 protected abstract boolean nodeEqual(Tree g)
Returns a boolean value indicating if this node is equal to the specified node. Children are not taken in consideration here. Even null vs non-null values are not compared.

Parameters:
g - node to compare with this
 o nodeCopy
 protected abstract Tree nodeCopy()
Clones a node without children

 o nextIndex
 public int nextIndex(int n)
Returns the index of the next non-null child. Null children are skipped. If there is no next child, then -1 is returned.

Parameters:
n - current index
 o firstIndex
 public int firstIndex()
Returns the index of the first non-null child or -1 if there are no children.

 o lastIndex
 public int lastIndex()
Returns the index of the last non-null child) or -1 if there are no children.

 o cutoff
 public void cutoff()
Cuts off all children from this.

 o getParent
 public Tree getParent()
Returns the parent of this node.

 o getRoot
 public Tree getRoot()
Returns the root.

 o parentIndex
 public int parentIndex()
Returns the index of this as a child of its parent.

 o depth
 public int depth()
Returns the number of edges between this node and the root.

 o iterator
 public TreeIterator iterator()
Creates an instance of TreeIterator for use in iteration over the nodes of the tree rooted at this.

 o isRoot
 public boolean isRoot()
Checks if this node is a tree root.

 o isLeaf
 public boolean isLeaf()
Checks if this node has no children.

 o relates
 public boolean relates(Tree d)
Checks if this and the the specified Tree have the same root.

Parameters:
d - tree whose root is compared with the root of this
 o contains
 public boolean contains(Tree d)
Checks if the specified Tree is a subtree of this.

Parameters:
d - tree to check for being a subtree of this
 o clone
 public Object clone()
Clones this tree. It may create a stand-alone tree out of a subtree.

Overrides:
clone in class Object
 o embed
 public synchronized void embed(Tree p,
                                int n)
Embeds the specified Tree as a child of this tree. The specified Tree replaces the specified child of this. The embedded tree should not be a subtree unless it is a subtree of this.

Parameters:
p - tree to embed
n - index of the child to be replaced
Throws: RuntimeException
index is out of bounds or an attempt is made to embed a subtree which is not a part of this tree or this is a slot
 o embedCopy
 public synchronized void embedCopy(Tree p,
                                    int n)
Clones the specified Tree and embeds it as a child of this tree. The copy of the specified Tree replaces the specified child of this.

Parameters:
p - tree to clone and embed
n - index of the child to be replaced
Throws: RuntimeException
index is out of bounds or this is a slot
 o insertNodeCopy
 public synchronized void insertNodeCopy(Tree d,
                                         int n)
Duplicates the tip node of the specified Tree and inserts it between this and its parent. This becomes the n-th child of the duplicated node. All other references of the duplicated node are set to null. This method can be modeled by other methods of class Tree but it is simpler and more efficient to use insertNodeCopy when it is necessary to insert new nodes into an existing tree.

Parameters:
d - tree whose tip inserted on atop of this
n - index of the reference to this
Throws: RuntimeException
null Tree parameter
 o substitute
 public synchronized void substitute(Tree p)
Substitutes the specified Tree for this. The specified Tree should not be a subtree unless it is a subtree of this.

Parameters:
p - tree to substitute
Throws: RuntimeException
this is a root or an attempt is made to substitute a subtree which is not a part of this tree
 o substituteCopy
 public synchronized void substituteCopy(Tree p)
Clones and substitutes the specified Tree for this.

Parameters:
p - tree to clone and substitute
Throws: RuntimeException
this is a root
 o congruent
 public boolean congruent(Tree r)
Compares the specified Tree with this. Returns a boolean indicating whether the two trees are equal, i.e. there is such one-to-one mapping between both the nodes and edges of the two trees that the contensts of the respective nodes are equal, which is checked by nodeEqual.

Parameters:
r - tree to compare with this
Returns:
true if the trees are equal
Throws: RuntimeException
this or the specified Tree is a slot
 o match
 public synchronized boolean match(Tree r)
Checks if this and the specified Tree match. Returns a boolean indicating whether they match. This may contain slots which play the role of variables matching any tree. Thus, this tree serves as a pattern. If the two trees match, then the counterparts of all slots become the first children of the trees associated with slots. Even if match yields false, still trees could be assigned to some trees associated with slots. The user can apply the method clean to cut the first children of the associated trees off. All slots rassociated with the same Tree should match congruent trees in order for match to succeed. If this method yields true, it means that there is such one-to-one mapping between the non-slot nodes of the two trees that all edges are also mapped one-to-one and the contensts of the respective nodes are equal, which is checked by nodeEqual.

Parameters:
r - tree to match against this
Returns:
true if this and the specified Tree match
See Also:
congruent, clean
 o clean
 public synchronized void clean()
Cuts off the first children of all trees associated with slots in this Tree. This method cleans a pattern tree to be matched against another one again.

 o instantiate
 public synchronized Tree instantiate()
Instantiates this Tree that is presumably a pattern. This is cloned and all slots in it are replaced by the trees are the first children of the trees associated with slots from this Tree.


All Packages  Class Hierarchy  This Package  Previous  Next  Index