et-forest.h revision 117395
1117395Skan/* Et-forest data structure implementation. 2117395Skan Copyright (C) 2002 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 16117395SkanFoundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 17117395Skan 18117395Skan/* 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 21117395Skan poly-logarithmic time for nearest common ancesto. 22117395Skan 23117395Skan ET tree strores its structue as a sequence of symbols obtained 24117395Skan by dfs(root) 25117395Skan 26117395Skan dfs (node) 27117395Skan { 28117395Skan s = node; 29117395Skan for each child c of node do 30117395Skan s = concat (s, c, node); 31117395Skan return s; 32117395Skan } 33117395Skan 34117395Skan For example for tree 35117395Skan 36117395Skan 1 37117395Skan / | \ 38117395Skan 2 3 4 39117395Skan / | 40117395Skan 4 5 41117395Skan 42117395Skan the sequence is 1 2 4 2 5 3 1 3 1 4 1. 43117395Skan 44117395Skan The sequence is stored in a sligtly 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 58117395Skantypedef struct et_forest *et_forest_t; 59117395Skantypedef struct et_forest_node *et_forest_node_t; 60117395Skan 61117395Skanextern et_forest_t et_forest_create PARAMS ((void)); 62117395Skan 63117395Skanextern void et_forest_delete PARAMS ((et_forest_t)); 64117395Skan 65117395Skanextern et_forest_node_t et_forest_add_node PARAMS ((et_forest_t, void *)); 66117395Skanextern int et_forest_add_edge PARAMS ((et_forest_t, et_forest_node_t, 67117395Skan et_forest_node_t)); 68117395Skanextern void et_forest_remove_node PARAMS ((et_forest_t, et_forest_node_t)); 69117395Skanextern int et_forest_remove_edge PARAMS ((et_forest_t, et_forest_node_t, 70117395Skan et_forest_node_t)); 71117395Skanextern et_forest_node_t et_forest_parent PARAMS ((et_forest_t, et_forest_node_t)); 72117395Skanextern et_forest_node_t et_forest_common_ancestor PARAMS ((et_forest_t, 73117395Skan et_forest_node_t, 74117395Skan et_forest_node_t)); 75117395Skanextern void * et_forest_node_value PARAMS ((et_forest_t, et_forest_node_t)); 76117395Skanextern int et_forest_enumerate_sons PARAMS ((et_forest_t, et_forest_node_t, 77117395Skan et_forest_node_t *)); 78117395Skan 79117395Skan#ifdef __cplusplus 80117395Skan} 81117395Skan#endif /* __cplusplus */ 82117395Skan 83117395Skan#endif /* _ET_TREE_H */ 84