java.lang.Object
- com.crawljax.stateabstractions.dom.RTED.RTED_InfoTree_Opt

```
public class RTED_InfoTree_Opt
extends Object
```
Computes the tree edit distance using RTED algorithm.

Author:

Mateusz Pawlik

Field Summary

Fields
Modifier and Type	Field	Description
`private static byte`	`BOTH`
`private double`	`costDel`
`private double`	`costIns`
`private double`	`costMatch`
`private long[][][]`	`costV`
`private long[][]`	`costW`
`long`	`counter`
`private double`	`da`
`private double`	`db`
`private double`	`dc`
`private double[][]`	`delta`
`private byte[][]`	`deltaBit`
`private static byte`	`HEAVY`
`private int[][]`	`IJ`
`private InfoTree`	`it1`
`private InfoTree`	`it2`
`private static byte`	`KR`
`private static byte`	`LEFT`
`private static byte`	`POST2_DESC_SUM`
`private static byte`	`POST2_KR_SUM`
`private static byte`	`POST2_LABEL`
`private static byte`	`POST2_LLD`
`private static byte`	`POST2_MIN_KR`
`private static byte`	`POST2_PARENT`
`private static byte`	`POST2_PRE`
`private static byte`	`POST2_REV_KR_SUM`
`private static byte`	`POST2_SIZE`
`private static byte`	`POST2_STRATEGY`
`private static byte`	`PRE2_POST`
`private int`	`previousStrategy`
`private static byte`	`REVHEAVY`
`private static byte`	`REVLEFT`
`private static byte`	`REVRIGHT`
`private static byte`	`RIGHT`
`private static byte`	`RKR`
`private static byte`	`RPOST2_MIN_RKR`
`private static byte`	`RPOST2_POST`
`private static byte`	`RPOST2_RLD`
`private int`	`size1`
`private int`	`size2`
`private int[][]`	`STR`
`int[]`	`strStat`
`private double[][]`	`t`

Constructor Summary

Constructors
Constructor Description

RTED_InfoTree_Opt(double delCost, double insCost, double matchCost)
The constructor.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private double`	`computeDistUsingStrArray(InfoTree it1, InfoTree it2)`	The recursion step according to the optimal strategy.
`private void`	`computeIJTable(InfoTree it, int subtreePreorder, int subtreeRevPreorder, int subtreeSize, int aStrategy, int treeSize)`	Computes an array where preorder/rev.preorder of a subforest of given subtree is stored and can be accessed for given i and j.
`void`	`computeOptimalStrategy()`	A method for computing and storing the optimal strategy
`private void`	`computePeriod(InfoTree it1, int aVp, int aNextVp, InfoTree it2, int aStrategy)`	Compute period method.
`void`	`init(LblTree t1, LblTree t2)`	Initialization method.
`private int`	`jOfI(InfoTree it, int aI, int aSubtreeWeight, int aSubtreeRevPre, int aSubtreePre, int aStrategy, int treeSize)`	Returns j for given i, result of j(i) form Demaine's algorithm.
`double`	`nonNormalizedTreeDist()`
`double`	`nonNormalizedTreeDist(LblTree t1, LblTree t2)`	Computes the tree edit distance between trees t1 and t2.
`void`	`setCustomCosts(double costDel, double costIns, double costMatch)`
`void`	`setCustomStrategy(int[][] strategyArray)`
`void`	`setCustomStrategy(int strategy, boolean ifSwitch)`
`private void`	`setDeltaBitValue(int a, int b, byte value, boolean switched)`
`private void`	`setDeltaValue(int a, int b, double value, boolean switched)`
`private double`	`spfH(InfoTree it1, InfoTree it2, int[] heavyPath)`	Single-path function for heavy path based on Klein/Demaine algorithm.
`private double`	`spfL(InfoTree it1, InfoTree it2)`	Single-path function for the left-most path based on Zhang and Shasha algorithm.
`private double`	`spfR(InfoTree it1, InfoTree it2)`	Single-path function for right-most path based on symmetric version of Zhang and Shasha algorithm.
`private void`	`treeEditDist(InfoTree it1, InfoTree it2, int i, int j)`
`private void`	`treeEditDistRev(InfoTree it1, InfoTree it2, int i, int j)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LEFT
```
private static final byte LEFT
```
See Also:

Constant Field Values

RIGHT
```
private static final byte RIGHT
```
See Also:

Constant Field Values

HEAVY
```
private static final byte HEAVY
```
See Also:

Constant Field Values

BOTH
```
private static final byte BOTH
```
See Also:

Constant Field Values

REVLEFT
```
private static final byte REVLEFT
```
See Also:

Constant Field Values

REVRIGHT
```
private static final byte REVRIGHT
```
See Also:

Constant Field Values

REVHEAVY
```
private static final byte REVHEAVY
```
See Also:

Constant Field Values

POST2_SIZE
```
private static final byte POST2_SIZE
```
See Also:

Constant Field Values

POST2_KR_SUM
```
private static final byte POST2_KR_SUM
```
See Also:

Constant Field Values

POST2_REV_KR_SUM
```
private static final byte POST2_REV_KR_SUM
```
See Also:

Constant Field Values

POST2_DESC_SUM
```
private static final byte POST2_DESC_SUM
```
See Also:

Constant Field Values

POST2_PRE
```
private static final byte POST2_PRE
```
See Also:

Constant Field Values

POST2_PARENT
```
private static final byte POST2_PARENT
```
See Also:

Constant Field Values

POST2_LABEL
```
private static final byte POST2_LABEL
```
See Also:

Constant Field Values

KR
```
private static final byte KR
```
See Also:

Constant Field Values

POST2_LLD
```
private static final byte POST2_LLD
```
See Also:

Constant Field Values

POST2_MIN_KR
```
private static final byte POST2_MIN_KR
```
See Also:

Constant Field Values

RKR
```
private static final byte RKR
```
See Also:

Constant Field Values

RPOST2_RLD
```
private static final byte RPOST2_RLD
```
See Also:

Constant Field Values

RPOST2_MIN_RKR
```
private static final byte RPOST2_MIN_RKR
```
See Also:

Constant Field Values

RPOST2_POST
```
private static final byte RPOST2_POST
```
See Also:

Constant Field Values

POST2_STRATEGY
```
private static final byte POST2_STRATEGY
```
See Also:

Constant Field Values

PRE2_POST
```
private static final byte PRE2_POST
```
See Also:

Constant Field Values

counter
```
public long counter
```

strStat
```
public final int[] strStat
```

it1
```
private InfoTree it1
```

it2
```
private InfoTree it2
```

size1
```
private int size1
```

size2
```
private int size2
```

STR
```
private int[][] STR
```

delta
```
private double[][] delta
```

deltaBit
```
private byte[][] deltaBit
```

t
```
private double[][] t
```

IJ
```
private int[][] IJ
```

costV
```
private long[][][] costV
```

costW
```
private long[][] costW
```

da
```
private double da
```

db
```
private double db
```

dc
```
private double dc
```

previousStrategy
```
private int previousStrategy
```

costDel
```
private double costDel
```

costIns
```
private double costIns
```

costMatch
```
private double costMatch
```

Constructor Detail
- RTED_InfoTree_Opt
```
public RTED_InfoTree_Opt(double delCost,
                         double insCost,
                         double matchCost)
```
  The constructor. Parameters passed are the edit operation costs.
  
  Parameters:
  
  delCost -
  
  insCost -
  
  matchCost -

Method Detail

nonNormalizedTreeDist
```
public double nonNormalizedTreeDist(LblTree t1,
                                    LblTree t2)
```
Computes the tree edit distance between trees t1 and t2.

Parameters:

t1 -

t2 -

Returns:

tree edit distance between trees t1 and t2

nonNormalizedTreeDist
```
public double nonNormalizedTreeDist()
```

init

public void init(LblTree t1,
                 LblTree t2)

Initialization method.

Parameters:: t1 -; t2 -

computeOptimalStrategy
```
public void computeOptimalStrategy()
```
A method for computing and storing the optimal strategy

computeDistUsingStrArray

private double computeDistUsingStrArray(InfoTree it1,
                                        InfoTree it2)

The recursion step according to the optimal strategy.

Parameters:: it1 -; it2 -
Returns:

spfL
```
private double spfL(InfoTree it1,
                    InfoTree it2)
```
Single-path function for the left-most path based on Zhang and Shasha algorithm.

Parameters:

it1 -

it2 -

Returns:

distance between subtrees it1 and it2

treeEditDist

private void treeEditDist(InfoTree it1,
                          InfoTree it2,
                          int i,
                          int j)

spfR
```
private double spfR(InfoTree it1,
                    InfoTree it2)
```
Single-path function for right-most path based on symmetric version of Zhang and Shasha algorithm.

Parameters:

it1 -

it2 -

Returns:

distance between subtrees it1 and it2

treeEditDistRev

private void treeEditDistRev(InfoTree it1,
                             InfoTree it2,
                             int i,
                             int j)

spfH
```
private double spfH(InfoTree it1,
                    InfoTree it2,
                    int[] heavyPath)
```
Single-path function for heavy path based on Klein/Demaine algorithm.

Parameters:

it1 -

it2 -

heavyPath -

Returns:

distance between subtrees it1 and it2

computePeriod

private void computePeriod(InfoTree it1,
                           int aVp,
                           int aNextVp,
                           InfoTree it2,
                           int aStrategy)

Compute period method.

Parameters:: it1 -; aVp -; aNextVp -; it2 -; aStrategy -

computeIJTable

private void computeIJTable(InfoTree it,
                            int subtreePreorder,
                            int subtreeRevPreorder,
                            int subtreeSize,
                            int aStrategy,
                            int treeSize)

Computes an array where preorder/rev.preorder of a subforest of given subtree is stored and can be accessed for given i and j.

Parameters:: it -; subtreePreorder -; subtreeRevPreorder -; subtreeSize -; aStrategy -; treeSize -

jOfI

private int jOfI(InfoTree it,
                 int aI,
                 int aSubtreeWeight,
                 int aSubtreeRevPre,
                 int aSubtreePre,
                 int aStrategy,
                 int treeSize)

Returns j for given i, result of j(i) form Demaine's algorithm.

Parameters:: it -; aI -; aSubtreeWeight -; aSubtreeRevPre -; aSubtreePre -; aStrategy -; treeSize -
Returns:: j for given i

setDeltaValue

private void setDeltaValue(int a,
                           int b,
                           double value,
                           boolean switched)

setDeltaBitValue

private void setDeltaBitValue(int a,
                              int b,
                              byte value,
                              boolean switched)

setCustomCosts

public void setCustomCosts(double costDel,
                           double costIns,
                           double costMatch)

setCustomStrategy

public void setCustomStrategy(int[][] strategyArray)

setCustomStrategy

public void setCustomStrategy(int strategy,
                              boolean ifSwitch)

Class RTED_InfoTree_Opt

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

LEFT

RIGHT

HEAVY

BOTH

REVLEFT

REVRIGHT

REVHEAVY

POST2_SIZE

POST2_KR_SUM

POST2_REV_KR_SUM

POST2_DESC_SUM

POST2_PRE

POST2_PARENT

POST2_LABEL

KR

POST2_LLD

POST2_MIN_KR

RKR

RPOST2_RLD

RPOST2_MIN_RKR

RPOST2_POST

POST2_STRATEGY

PRE2_POST

counter

strStat

it1

it2

size1

size2

STR

delta

deltaBit

t

IJ

costV

costW

da

db

dc

previousStrategy

costDel

costIns

costMatch

Constructor Detail

RTED_InfoTree_Opt

Method Detail

nonNormalizedTreeDist

nonNormalizedTreeDist

init

computeOptimalStrategy

computeDistUsingStrArray

spfL

treeEditDist

spfR

treeEditDistRev

spfH

computePeriod

computeIJTable

jOfI

setDeltaValue

setDeltaBitValue

setCustomCosts

setCustomStrategy

setCustomStrategy