#include <et-forest.h>

Collaboration diagram for et_node:

Data Fields
void *	data

int	dfs_num_in

int	dfs_num_out

struct et_node *	father

struct et_node *	son

struct et_node *	left

struct et_node *	right

struct et_occ *	rightmost_occ

struct et_occ *	parent_occ

Detailed Description

Et-forest data structure implementation.
Copyright (C) 2002-2024 Free Software Foundation, Inc.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.

This package implements ET forest data structure. Each tree in
the structure maintains a tree structure and offers logarithmic time
for tree operations (insertion and removal of nodes and edges) and
poly-logarithmic time for nearest common ancestor.

ET tree stores its structure as a sequence of symbols obtained
by dfs(root)

dfs (node)
{
  s = node;
  for each child c of node do
    s = concat (s, c, node);
  return s;
}

For example for tree

         1
       / | \
      2  3  4
    / |
   4  5

the sequence is 1 2 4 2 5 3 1 3 1 4 1.

The sequence is stored in a slightly modified splay tree.
In order to support various types of node values, a hashtable
is used to convert node values to the internal representation.

The node representing the node in an et tree.

Field Documentation

◆ data

void* et_node::data

Referenced by et_new_tree(), first_dom_son(), get_immediate_dominator(), nearest_common_dominator(), next_dom_son(), root_of_dom_tree(), and set_immediate_dominator().

◆ dfs_num_in

int et_node::dfs_num_in

Referenced by assign_dfs_numbers(), bb_dom_dfs_in(), and dominated_by_p().

◆ dfs_num_out

int et_node::dfs_num_out

Referenced by assign_dfs_numbers(), bb_dom_dfs_out(), and dominated_by_p().

◆ father

struct et_node* et_node::father

Referenced by assign_dfs_numbers(), compute_dom_fast_query(), compute_dom_fast_query_in_region(), et_free_tree(), et_set_father(), et_split(), get_immediate_dominator(), next_dom_son(), and set_immediate_dominator().

◆ left

struct et_node* et_node::left

Referenced by et_set_father(), and et_split().

◆ parent_occ

struct et_occ* et_node::parent_occ

Referenced by et_free_tree_force(), et_set_father(), and et_split().

◆ right

struct et_node* et_node::right

Referenced by assign_dfs_numbers(), et_set_father(), et_split(), and next_dom_son().

◆ rightmost_occ

struct et_occ* et_node::rightmost_occ

Referenced by et_below(), et_free_tree(), et_free_tree_force(), et_nca(), et_root(), et_set_father(), and et_split().

◆ son

struct et_node* et_node::son

Referenced by assign_dfs_numbers(), et_free_tree(), et_set_father(), et_split(), first_dom_son(), get_dominated_by(), and next_dom_son().

The documentation for this struct was generated from the following file:

et-forest.h

Data Fields