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