Class Node

java.lang.Object
  |
  +--Node

Direct Known Subclasses:

FunctionCallNode, VariableNode

public abstract class Node

extends Object

This class provides a skeletal implementation of a term. It is an expression tree node.

Author:

P. URSO

Field Summary

static int	MAX_PRIORITY The highest priority for an induction variable.
static int	MIN_PRIORITY The lowest priority for an induction variable.

Constructor Summary

Node()

Method Summary

abstract Node	applySubst(Substitution sigma) Applies a substitution to this term.
Node	bot(Path p) Computes bottom part of the term.
Path	botPath() Compute MAXIMUN BOTTOM PATH.
Path	find(Node node) Find the path to a substerm in a term.
boolean	getAsPart(Node node) Tests if this term as an other as part.
abstract int	getNumber(Type t) Returns number of sub term with a specified type of this node.
Node	getSubterm(Path p) Gives subterm at specified path.
abstract Type	getType() Returns the type of the term.
abstract void	getVariables(Set vars) Extends the set of variables apparing in this term.
abstract boolean	greaterThan(Node node) Tests if this term is greater (in order) than an other.
abstract void	inductionVariables(Map iv, int priority) Extends the map of induction variable with the ones of this term.
boolean	isConstant() Indicates if this term is a constant.
boolean	isConstructorRooted() Tests if this term is rooted by a constructor symbol.
boolean	isGround() Indicates if this term is ground.
abstract void	makeFilter(Node node, Substitution sigma) Constructs a filter between this term and an other.
Node	nbt(Path p) Computes nbt part of the term.
Node	ntp(Path p) Computes npt part of the term.
int	numAsPart(Node node) Counts how many times this term as an other as part.
Node	remplaceSubterm(Path p, Node n) Remplace subterm at specified path by an other.
Node	top(Path p) Computes top part of the term.
Path	topPath() Compute MAXIMUN TOP PATH.
protected String	toStringInfix() Returns a string representation of this term when it is an argument of an infix call.
Node	withNewVariables() Remplaces varia1bles in term by new variables.

Methods inherited from class java.lang.Object

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

Field Detail

MAX_PRIORITY

public static final int MAX_PRIORITY

The highest priority for an induction variable.

MIN_PRIORITY

public static final int MIN_PRIORITY

The lowest priority for an induction variable.

Constructor Detail

Node

public Node()

Method Detail

getType

public abstract Type getType()

Returns the type of the term.

Returns:

the type of the node.

applySubst

public abstract Node applySubst(Substitution sigma)

Applies a substitution to this term.

Parameters:

sigma - the substitution map.

Returns:

a new node where all terms mapped in the substitution are remplaced by theirs image.

makeFilter

public abstract void makeFilter(Node node,
                                Substitution sigma)
                         throws SubstitutionStop

Constructs a filter between this term and an other. If making such a filter is not possible, throws a SubstitutionStop.

Parameters:

node - the other term.

sigma - the substitution map in construction.

Throws:

SubstitutionStop -

greaterThan

public abstract boolean greaterThan(Node node)

Tests if this term is greater (in order) than an other.

Parameters:

node - the other term.

getAsPart

public boolean getAsPart(Node node)

Tests if this term as an other as part.

Parameters:

node - the other term.

Returns:

true if the terms are "equals".

numAsPart

public int numAsPart(Node node)

Counts how many times this term as an other as part.

Parameters:

node - the other term.

Returns:

1 if the terms are "equals", 0 otherwise.

find

public Path find(Node node)

Find the path to a substerm in a term. !Eavy algorithm!.

Parameters:

node - the subterm.

topPath

public Path topPath()

Compute MAXIMUN TOP PATH.

Returns:

the top path (Empty by default).

botPath

public Path botPath()

Compute MAXIMUN BOTTOM PATH.

Returns:

the bottom path (Empty by default).

top

public Node top(Path p)

Computes top part of the term.

Parameters:

p - a top path.

Returns:

top(t) -- this if p is Empty, null otherwise (error).

ntp

public Node ntp(Path p)

Computes npt part of the term.

Parameters:

p - a top path.

Returns:

npt(t) -- constant of node's type if p is Empty, null otherwise (error).

bot

public Node bot(Path p)

Computes bottom part of the term.

Parameters:

p - a bottom path.

Returns:

bot(t) -- this if p is Empty, null otherwise (error).

nbt

public Node nbt(Path p)

Computes nbt part of the term.

Parameters:

p - a bottom path.

Returns:

nbt(t) -- constant of node's type if p is Empty, null otherwise (error).

inductionVariables

public abstract void inductionVariables(Map iv,
                                        int priority)

Extends the map of induction variable with the ones of this term. Variables are mapped with their maximum induction priority. Priority is 3 for variable always in induction position, 2 for variable finally in induction position, 1 for variable passed by an induction position, 0 for variable in empty position, -1 for variable never in induction position.

Parameters:

iv - the map in construction.

priority - the current priority.

getVariables

public abstract void getVariables(Set vars)

Extends the set of variables apparing in this term.

Parameters:

vars - the set of variables in construction.

getSubterm

public Node getSubterm(Path p)

Gives subterm at specified path.

Parameters:

p - path to subterm.

Returns:

t / p = this node if p == null, null otherwise.

remplaceSubterm

public Node remplaceSubterm(Path p,
                            Node n)

Remplace subterm at specified path by an other.

Parameters:

p - path to subterm.

n - node to put at path.

Returns:

t[n]_p = n if p == null, null otherwise.

withNewVariables

public Node withNewVariables()

Remplaces varia1bles in term by new variables.

isGround

public boolean isGround()

Indicates if this term is ground.

Returns:

true it gets no variables.

isConstant

public boolean isConstant()

Indicates if this term is a constant.

Returns:

false.

isConstructorRooted

public boolean isConstructorRooted()

Tests if this term is rooted by a constructor symbol.

Returns:

false, by default.

getNumber

public abstract int getNumber(Type t)

Returns number of sub term with a specified type of this node.

Parameters:

t - the type.

toStringInfix

protected String toStringInfix()

Returns a string representation of this term when it is an argument of an infix call.

Returns:

a string representation of this term.

See Also:

FunctionCallNode