Type Alias IdArray 

type IdArray<'n, N> = Vec<(usize, Option<Identifier<'n, N>>)>;

A cache that contains the postorder index and the identifier of TreeNodes by the preorder index of the nodes.

This cache is filled by CSEVisitor during the first traversal and is used by CSERewriter during the second traversal.

The purpose of this cache is to quickly find the identifier of a node during the second traversal.

Elements in this array are added during f_down so the indexes represent the preorder index of nodes and thus element 0 belongs to the root of the tree.

The elements of the array are tuples that contain:

• Postorder index that belongs to the preorder index. Assigned during f_up, start from 0.
• The optional Identifier of the node. If none the node should not be considered for CSE.

Example

An expression tree like (a + b) would have the following IdArray:

[
  (2, Some(Identifier(hash_of("a + b"), &"a + b"))),
  (1, Some(Identifier(hash_of("a"), &"a"))),
  (0, Some(Identifier(hash_of("b"), &"b")))
]

Aliased Type

struct IdArray<'n, N> { /* private fields */ }