1132718Skan/* Et-forest data structure implementation. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3117395Skan 4117395SkanThis program is free software; you can redistribute it and/or modify 5117395Skanit under the terms of the GNU General Public License as published by 6117395Skanthe Free Software Foundation; either version 2 of the License, or 7117395Skan(at your option) any later version. 8117395Skan 9117395SkanThis program is distributed in the hope that it will be useful, 10117395Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 11117395SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12117395SkanGNU General Public License for more details. 13117395Skan 14117395SkanYou should have received a copy of the GNU General Public License 15117395Skanalong with this program; if not, write to the Free Software 16169689SkanFoundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17117395Skan 18132718Skan/* This package implements ET forest data structure. Each tree in 19117395Skan the structure maintains a tree structure and offers logarithmic time 20117395Skan for tree operations (insertion and removal of nodes and edges) and 21132718Skan poly-logarithmic time for nearest common ancestor. 22132718Skan 23132718Skan ET tree stores its structure as a sequence of symbols obtained 24117395Skan by dfs(root) 25117395Skan 26132718Skan dfs (node) 27117395Skan { 28117395Skan s = node; 29117395Skan for each child c of node do 30117395Skan s = concat (s, c, node); 31117395Skan return s; 32117395Skan } 33132718Skan 34117395Skan For example for tree 35132718Skan 36117395Skan 1 37117395Skan / | \ 38117395Skan 2 3 4 39117395Skan / | 40117395Skan 4 5 41132718Skan 42117395Skan the sequence is 1 2 4 2 5 3 1 3 1 4 1. 43132718Skan 44132718Skan The sequence is stored in a slightly modified splay tree. 45117395Skan In order to support various types of node values, a hashtable 46117395Skan is used to convert node values to the internal representation. */ 47117395Skan 48117395Skan#ifndef _ET_TREE_H 49117395Skan#define _ET_TREE_H 50117395Skan 51117395Skan#include <ansidecl.h> 52117395Skan#include <stddef.h> 53117395Skan 54117395Skan#ifdef __cplusplus 55117395Skanextern "C" { 56117395Skan#endif /* __cplusplus */ 57117395Skan 58132718Skan/* The node representing the node in an et tree. */ 59132718Skanstruct et_node 60132718Skan{ 61132718Skan void *data; /* The data represented by the node. */ 62117395Skan 63132718Skan int dfs_num_in, dfs_num_out; /* Number of the node in the dfs ordering. */ 64117395Skan 65132718Skan struct et_node *father; /* Father of the node. */ 66132718Skan struct et_node *son; /* The first of the sons of the node. */ 67132718Skan struct et_node *left; 68132718Skan struct et_node *right; /* The brothers of the node. */ 69117395Skan 70169689Skan struct et_occ *rightmost_occ; /* The rightmost occurrence. */ 71169689Skan struct et_occ *parent_occ; /* The occurrence of the parent node. */ 72132718Skan}; 73117395Skan 74132718Skanstruct et_node *et_new_tree (void *data); 75132718Skanvoid et_free_tree (struct et_node *); 76169689Skanvoid et_free_tree_force (struct et_node *); 77169689Skanvoid et_free_pools (void); 78132718Skanvoid et_set_father (struct et_node *, struct et_node *); 79132718Skanvoid et_split (struct et_node *); 80132718Skanstruct et_node *et_nca (struct et_node *, struct et_node *); 81132718Skanbool et_below (struct et_node *, struct et_node *); 82132718Skan 83117395Skan#ifdef __cplusplus 84117395Skan} 85117395Skan#endif /* __cplusplus */ 86117395Skan 87117395Skan#endif /* _ET_TREE_H */ 88