java.lang.Object
- com.crawljax.stateabstractions.dom.apted.node.NodeIndexer<D,C>

Type Parameters:

D - type of node data.

C - type of cost model.
```
public class NodeIndexer<D,C extends CostModel>
extends Object
```
Indexes nodes of the input tree to the algorithm that is already parsed to tree structure using AptedNode class. Stores various indices on nodes required for efficient computation of APTED [1,2]. Additionally, it stores single-value properties of the tree.
For indexing we use four tree traversals that assign ids to the nodes:
- left-to-right preorder [1],
- right-to-left preorder [1],
- left-to-right postorder [2],
- right-to-left postorder [2].
See the source code for more algorithm-related comments.
References:
- [1] M. Pawlik and N. Augsten. Efficient Computation of the Tree Edit Distance. ACM Transactions on Database Systems (TODS) 40(1). 2015.
- [2] M. Pawlik and N. Augsten. Tree edit distance: Robust and memory- efficient. Information Systems 56. 2016.
See Also:

AptedNode, InputParser

Field Summary

Fields
Modifier and Type	Field	Description
`int[][]`	`children`	Index from left-to-right preorder id of node n (starting with `0`) to the array of n's children.
`private C`	`costModel`
`private int`	`currentNode`	Stores the left-to-right preorder id of the current subtree's root node.
`private int`	`descSizesTmp`	Temporary variable used in indexing for storing sum of subtree sizes rooted at descendant nodes.
`private int`	`krSizesSumTmp`	Temporary variable used in indexing for storing sum of keyroot node sizes.
`int`	`lchl`	Stores the number of leftmost-child leaf nodes in the input tree [2, Section 5.3].
`boolean[]`	`nodeType_L`	Index from left-to-right preorder id of node n (starting with `0`) to a boolean value that states if node n lies on the leftmost path starting at n's parent [2, Algorithm 1, Lines 26,36].
`boolean[]`	`nodeType_R`	Index from left-to-right preorder id of node n (starting with `0`) to a boolean value that states if node n lies on the rightmost path starting at n's parent input tree [2, Section 5.3, Algorithm 1, Lines 26,36].
`int[]`	`parents`	Index from left-to-right preorder id of node n (starting with `0`) to the left-to-right preorder id of n's parent.
`int[]`	`postL_to_lld`	Index from left-to-right postorder id of node n (starting with `0`) to the left-to-right postorder id of n's leftmost leaf descendant.
`int[]`	`postL_to_preL`	Index from left-to-right postorder id of node n (starting with `0`) to the left-to-right preorder id of n.
`int[]`	`postR_to_preL`	Index from right-to-left postorder id of node n (starting with `0`) to the left-to-right preorder id of n.
`int[]`	`postR_to_rld`	Index from right-to-left postorder id of node n (starting with `0`) to the right-to-left postorder id of n's rightmost leaf descendant.
`int[]`	`preL_to_desc_sum`	Index from left-to-right preorder id of node n (starting with `0`) to the cost of spf_A (single path function using an inner path) for the subtree rooted at n [1, Section 5.2].
`int[]`	`preL_to_kr_sum`	Index from left-to-right preorder id of node n (starting with `0`) to the cost of spf_L (single path function using the leftmost path) for the subtree rooted at n [1, Section 5.2].
`int[]`	`preL_to_ln`	Index from left-to-right preorder id of node n (starting with `0`) to the left-to-right preorder id of the first leaf node to the left of n.
`AptedNode<D>[]`	`preL_to_node`	Index from left-to-right preorder id of node n (starting with `0`) to AptedNode object corresponding to n.
`int[]`	`preL_to_postL`	Index from left-to-right preorder id of node n (starting with `0`) to the left-to-right postorder id of n.
`int[]`	`preL_to_postR`	Index from left-to-right preorder id of node n (starting with `0`) to the right-to-left postorder id of n.
`int[]`	`preL_to_preR`	Index from left-to-right preorder id of node n (starting with `0`) to the right-to-left preorder id of n.
`int[]`	`preL_to_rev_kr_sum`	Index from left-to-right preorder id of node n (starting with `0`) to the cost of spf_R (single path function using the rightmost path) for the subtree rooted at n [1, Section 5.2].
`float[]`	`preL_to_sumDelCost`	Index from left-to-right preorder id of node n (starting with `0`) to the cost of deleting all nodes in the subtree rooted at n.
`float[]`	`preL_to_sumInsCost`	Index from left-to-right preorder id of node n (starting with `0`) to the cost of inserting all nodes in the subtree rooted at n.
`private int`	`preorderTmp`	Temporary variable used in indexing for storing preorder index of a node.
`int[]`	`preR_to_ln`	Index from right-to-left preorder id of node n (starting with `0`) to the right-to-left preorder id of the first leaf node to the right of n.
`int[]`	`preR_to_preL`	Index from right-to-left preorder id of node n (starting with `0`) to the left-to-right preorder id of n.
`int`	`rchl`	Stores the number of rightmost-child leaf nodes in the input tree [2, Section 5.3].
`private int`	`revkrSizesSumTmp`	Temporary variable used in indexing for storing sum of right-to-left keyroot node sizes.
`int[]`	`sizes`	Index from left-to-right preorder id of node n (starting with `0`) to the size of n's subtree (node n and all its descendants).
`private int`	`sizeTmp`	Temporary variable used in indexing for storing subtree size.
`private int`	`treeSize`	Stores the size of the input tree.

Constructor Summary

Constructors
Constructor	Description
`NodeIndexer(AptedNode<D> inputTree, C costModel)`	Indexes the nodes of input trees and stores the indices for quick access from APTED algorithm.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`int`	`getCurrentNode()`	Returns the root node of the currently processed subtree in the tree decomposition part of APTED [1, Algorithm 1].
`int`	`getSize()`	Returns the number of nodes in the input tree.
`private int`	`indexNodes(AptedNode<D> node, int postorder)`	Indexes the nodes of the input tree.
`boolean`	`isLeaf(int node)`	Verifies if node is a leaf.
`AptedNode<D>`	`postL_to_node(int postL)`	An abbreviation that uses indices to retrieve pointer to `AptedNode` of the given node.
`AptedNode<D>`	`postR_to_node(int postR)`	An abbreviation that uses indices to retrieve pointer to `AptedNode` of the given node.
`private void`	`postTraversalIndexing()`	Indexes the nodes of the input tree.
`int`	`preL_to_lld(int preL)`	An abbreviation that uses indices to calculate the left-to-right preorder id of the leftmost leaf node of the given node.
`int`	`preL_to_rld(int preL)`	An abbreviation that uses indices to calculate the left-to-right preorder id of the rightmost leaf node of the given node.
`void`	`setCurrentNode(int preorder)`	Stores the root nodes's preorder id of the currently processes subtree.
`private int[]`	`toIntArray(ArrayList<Integer> integers)`	Converts `ArrayList` of integer values to an array.

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

- Field Detail
  - preL_to_node
```
public final AptedNode<D>[] preL_to_node
```
    Index from left-to-right preorder id of node n (starting with 0) to AptedNode object corresponding to n. Used for cost of edit operations.
    
    See Also:
    
    AptedNode
  - sizes
```
public final int[] sizes
```
    Index from left-to-right preorder id of node n (starting with 0) to the size of n's subtree (node n and all its descendants).
  - parents
```
public final int[] parents
```
    Index from left-to-right preorder id of node n (starting with 0) to the left-to-right preorder id of n's parent.
  - children
```
public final int[][] children
```
    Index from left-to-right preorder id of node n (starting with 0) to the array of n's children. Size of children array at node n equals the number of n's children.
  - postL_to_lld
```
public final int[] postL_to_lld
```
    Index from left-to-right postorder id of node n (starting with 0) to the left-to-right postorder id of n's leftmost leaf descendant.
  - postR_to_rld
```
public final int[] postR_to_rld
```
    Index from right-to-left postorder id of node n (starting with 0) to the right-to-left postorder id of n's rightmost leaf descendant.
  - preL_to_ln
```
public final int[] preL_to_ln
```
    Index from left-to-right preorder id of node n (starting with 0) to the left-to-right preorder id of the first leaf node to the left of n. If there is no leaf node to the left of n, it is represented with the value -1 [1, Section 8.4].
  - preR_to_ln
```
public final int[] preR_to_ln
```
    Index from right-to-left preorder id of node n (starting with 0) to the right-to-left preorder id of the first leaf node to the right of n. If there is no leaf node to the right of n, it is represented with the value -1 [1, Section 8.4].
  - nodeType_L
```
public final boolean[] nodeType_L
```
    Index from left-to-right preorder id of node n (starting with 0) to a boolean value that states if node n lies on the leftmost path starting at n's parent [2, Algorithm 1, Lines 26,36].
  - nodeType_R
```
public final boolean[] nodeType_R
```
    Index from left-to-right preorder id of node n (starting with 0) to a boolean value that states if node n lies on the rightmost path starting at n's parent input tree [2, Section 5.3, Algorithm 1, Lines 26,36].
  - preL_to_preR
```
public final int[] preL_to_preR
```
    Index from left-to-right preorder id of node n (starting with 0) to the right-to-left preorder id of n.
  - preR_to_preL
```
public final int[] preR_to_preL
```
    Index from right-to-left preorder id of node n (starting with 0) to the left-to-right preorder id of n.
  - preL_to_postL
```
public final int[] preL_to_postL
```
    Index from left-to-right preorder id of node n (starting with 0) to the left-to-right postorder id of n.
  - postL_to_preL
```
public final int[] postL_to_preL
```
    Index from left-to-right postorder id of node n (starting with 0) to the left-to-right preorder id of n.
  - preL_to_postR
```
public final int[] preL_to_postR
```
    Index from left-to-right preorder id of node n (starting with 0) to the right-to-left postorder id of n.
  - postR_to_preL
```
public final int[] postR_to_preL
```
    Index from right-to-left postorder id of node n (starting with 0) to the left-to-right preorder id of n.
  - preL_to_kr_sum
```
public final int[] preL_to_kr_sum
```
    Index from left-to-right preorder id of node n (starting with 0) to the cost of spf_L (single path function using the leftmost path) for the subtree rooted at n [1, Section 5.2].
  - preL_to_rev_kr_sum
```
public final int[] preL_to_rev_kr_sum
```
    Index from left-to-right preorder id of node n (starting with 0) to the cost of spf_R (single path function using the rightmost path) for the subtree rooted at n [1, Section 5.2].
  - preL_to_desc_sum
```
public final int[] preL_to_desc_sum
```
    Index from left-to-right preorder id of node n (starting with 0) to the cost of spf_A (single path function using an inner path) for the subtree rooted at n [1, Section 5.2].
  - preL_to_sumDelCost
```
public final float[] preL_to_sumDelCost
```
    Index from left-to-right preorder id of node n (starting with 0) to the cost of deleting all nodes in the subtree rooted at n.
  - preL_to_sumInsCost
```
public final float[] preL_to_sumInsCost
```
    Index from left-to-right preorder id of node n (starting with 0) to the cost of inserting all nodes in the subtree rooted at n.
  - lchl
```
public int lchl
```
    Stores the number of leftmost-child leaf nodes in the input tree [2, Section 5.3].
  - rchl
```
public int rchl
```
    Stores the number of rightmost-child leaf nodes in the input tree [2, Section 5.3].
  - currentNode
```
private int currentNode
```
    Stores the left-to-right preorder id of the current subtree's root node. Used in the tree decomposition phase of APTED [1, Algorithm 1].
  - treeSize
```
private final int treeSize
```
    Stores the size of the input tree.
  - sizeTmp
```
private int sizeTmp
```
    Temporary variable used in indexing for storing subtree size.
  - descSizesTmp
```
private int descSizesTmp
```
    Temporary variable used in indexing for storing sum of subtree sizes rooted at descendant nodes.
  - krSizesSumTmp
```
private int krSizesSumTmp
```
    Temporary variable used in indexing for storing sum of keyroot node sizes.
  - revkrSizesSumTmp
```
private int revkrSizesSumTmp
```
    Temporary variable used in indexing for storing sum of right-to-left keyroot node sizes.
  - preorderTmp
```
private int preorderTmp
```
    Temporary variable used in indexing for storing preorder index of a node.
  - costModel
```
private final C extends CostModel costModel
```
- Constructor Detail
  - NodeIndexer
```
public NodeIndexer(AptedNode<D> inputTree,
                   C costModel)
```
    Indexes the nodes of input trees and stores the indices for quick access from APTED algorithm.
    
    Parameters:
    
    inputTree - an input tree to APTED. Its nodes will be indexed.
    
    costModel - instance of a cost model to compute preL_to_sumDelCost and preL_to_sumInsCost.
- Method Detail
  - indexNodes
```
private int indexNodes(AptedNode<D> node,
                       int postorder)
```
    Indexes the nodes of the input tree. Stores information about each tree node in index arrays. It computes the following indices: parents, children, nodeType_L, nodeType_R, preL_to_desc_sum, preL_to_kr_sum, preL_to_rev_kr_sum, preL_to_node, sizes, preL_to_preR, preR_to_preL, postL_to_preL, preL_to_postL, preL_to_postR, postR_to_preL.
    It is a recursive method that traverses the tree once.
    
    Parameters:
    
    node - is the current node while traversing the input tree.
    
    postorder - is the postorder id of the current node.
    
    Returns:
    
    postorder id of the current node.
  - postTraversalIndexing
```
private void postTraversalIndexing()
```
    Indexes the nodes of the input tree. It computes the following indices, which could not be computed immediately while traversing the tree in indexNodes(com.crawljax.stateabstractions.dom.apted.node.AptedNode<D>, int): preL_to_ln, postL_to_lld, postR_to_rld, preR_to_ln.
    Runs in linear time in the input tree size. Currently requires two loops over input tree nodes. Can be reduced to one loop (see the code).
  - preL_to_lld
```
public int preL_to_lld(int preL)
```
    An abbreviation that uses indices to calculate the left-to-right preorder id of the leftmost leaf node of the given node.
    
    Parameters:
    
    preL - left-to-right preorder id of a node.
    
    Returns:
    
    left-to-right preorder id of the leftmost leaf node of preL.
  - preL_to_rld
```
public int preL_to_rld(int preL)
```
    An abbreviation that uses indices to calculate the left-to-right preorder id of the rightmost leaf node of the given node.
    
    Parameters:
    
    preL - left-to-right preorder id of a node.
    
    Returns:
    
    left-to-right preorder id of the rightmost leaf node of preL.
  - postL_to_node
```
public AptedNode<D> postL_to_node(int postL)
```
    An abbreviation that uses indices to retrieve pointer to AptedNode of the given node.
    
    Parameters:
    
    postL - left-to-right postorder id of a node.
    
    Returns:
    
    AptedNode corresponding to postL.
  - postR_to_node
```
public AptedNode<D> postR_to_node(int postR)
```
    An abbreviation that uses indices to retrieve pointer to AptedNode of the given node.
    
    Parameters:
    
    postR - right-to-left postorder id of a node.
    
    Returns:
    
    AptedNode corresponding to postR.
  - getSize
```
public int getSize()
```
    Returns the number of nodes in the input tree.
    
    Returns:
    
    number of nodes in the tree.
  - isLeaf
```
public boolean isLeaf(int node)
```
    Verifies if node is a leaf.
    
    Parameters:
    
    node - preorder id of a node to verify.
    
    Returns:
    
    true if node is a leaf, false otherwise.
  - toIntArray
```
private int[] toIntArray(ArrayList<Integer> integers)
```
    Converts ArrayList of integer values to an array. Reads all items in the list and copies to the output array. The size of output array equals the number of elements in the list.
    
    Parameters:
    
    integers - ArrayList with integer values.
    
    Returns:
    
    array with values from input ArrayList.
  - getCurrentNode
```
public int getCurrentNode()
```
    Returns the root node of the currently processed subtree in the tree decomposition part of APTED [1, Algorithm 1]. At each point, we have to know which subtree do we process.
    
    Returns:
    
    current subtree root node.
  - setCurrentNode
```
public void setCurrentNode(int preorder)
```
    Stores the root nodes's preorder id of the currently processes subtree.
    
    Parameters:
    
    preorder - preorder id of the root node.

Class NodeIndexer<D,​C extends CostModel>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

preL_to_node

sizes

parents

children

postL_to_lld

postR_to_rld

preL_to_ln

preR_to_ln

nodeType_L

nodeType_R

preL_to_preR

preR_to_preL

preL_to_postL

postL_to_preL

preL_to_postR

postR_to_preL

preL_to_kr_sum

preL_to_rev_kr_sum

preL_to_desc_sum

preL_to_sumDelCost

preL_to_sumInsCost

lchl

rchl

currentNode

treeSize

sizeTmp

descSizesTmp

krSizesSumTmp

revkrSizesSumTmp

preorderTmp

costModel

Constructor Detail

NodeIndexer

Method Detail

indexNodes

postTraversalIndexing

preL_to_lld

preL_to_rld

postL_to_node

postR_to_node

getSize

isLeaf

toIntArray

getCurrentNode

setCurrentNode

Class NodeIndexer<D,C extends CostModel>