1  /* Et-forest data structure implementation.
       2     Copyright (C) 2002-2023 Free Software Foundation, Inc.
       3  
       4     This program is free software; you can redistribute it and/or modify
       5     it under the terms of the GNU General Public License as published by
       6     the Free Software Foundation; either version 3 of the License, or
       7     (at your option) any later version.
       8  
       9     This program is distributed in the hope that it will be useful,
      10     but WITHOUT ANY WARRANTY; without even the implied warranty of
      11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12     GNU General Public License for more details.
      13  
      14     You should have received a copy of the GNU General Public License
      15     along with this program; see the file COPYING3.  If not see
      16     <http://www.gnu.org/licenses/>.  */
      17  
      18  /* This package implements ET forest data structure. Each tree in
      19     the structure maintains a tree structure and offers logarithmic time
      20     for tree operations (insertion and removal of nodes and edges) and
      21     poly-logarithmic time for nearest common ancestor.
      22  
      23     ET tree stores its structure as a sequence of symbols obtained
      24     by dfs(root)
      25  
      26     dfs (node)
      27     {
      28       s = node;
      29       for each child c of node do
      30         s = concat (s, c, node);
      31       return s;
      32     }
      33  
      34     For example for tree
      35  
      36              1
      37            / | \
      38           2  3  4
      39         / |
      40        4  5
      41  
      42     the sequence is 1 2 4 2 5 3 1 3 1 4 1.
      43  
      44     The sequence is stored in a slightly modified splay tree.
      45     In order to support various types of node values, a hashtable
      46     is used to convert node values to the internal representation.  */
      47  
      48  #ifndef _ET_TREE_H
      49  #define _ET_TREE_H
      50  
      51  #ifdef __cplusplus
      52  extern "C" {
      53  #endif /* __cplusplus */
      54  
      55  /* The node representing the node in an et tree.  */
      56  struct et_node
      57  {
      58    void *data;			/* The data represented by the node.  */
      59  
      60    int dfs_num_in, dfs_num_out;	/* Number of the node in the dfs ordering.  */
      61  
      62    struct et_node *father;	/* Father of the node.  */
      63    struct et_node *son;		/* The first of the sons of the node.  */
      64    struct et_node *left;
      65    struct et_node *right;	/* The brothers of the node.  */
      66  
      67    struct et_occ *rightmost_occ;	/* The rightmost occurrence.  */
      68    struct et_occ *parent_occ;	/* The occurrence of the parent node.  */
      69  };
      70  
      71  struct et_node *et_new_tree (void *data);
      72  void et_free_tree (struct et_node *);
      73  void et_free_tree_force (struct et_node *);
      74  void et_free_pools (void);
      75  void et_set_father (struct et_node *, struct et_node *);
      76  void et_split (struct et_node *);
      77  struct et_node *et_nca (struct et_node *, struct et_node *);
      78  bool et_below (struct et_node *, struct et_node *);
      79  struct et_node *et_root (struct et_node *);
      80  
      81  #ifdef __cplusplus
      82  }
      83  #endif /* __cplusplus */
      84  
      85  #endif /* _ET_TREE_H */