| /* Et-forest data structure implementation. |
| Copyright (C) 2002 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 2 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; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ |
| |
| /* 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 ancesto. |
| |
| ET tree strores its structue 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 sligtly modified splay tree. |
| In order to support various types of node values, a hashtable |
| is used to convert node values to the internal representation. */ |
| |
| #ifndef _ET_TREE_H |
| #define _ET_TREE_H |
| |
| #include <ansidecl.h> |
| #include <stddef.h> |
| |
| #ifdef __cplusplus |
| extern "C" { |
| #endif /* __cplusplus */ |
| |
| typedef struct et_forest *et_forest_t; |
| typedef struct et_forest_node *et_forest_node_t; |
| |
| extern et_forest_t et_forest_create PARAMS ((void)); |
| |
| extern void et_forest_delete PARAMS ((et_forest_t)); |
| |
| extern et_forest_node_t et_forest_add_node PARAMS ((et_forest_t, void *)); |
| extern int et_forest_add_edge PARAMS ((et_forest_t, et_forest_node_t, |
| et_forest_node_t)); |
| extern void et_forest_remove_node PARAMS ((et_forest_t, et_forest_node_t)); |
| extern int et_forest_remove_edge PARAMS ((et_forest_t, et_forest_node_t, |
| et_forest_node_t)); |
| extern et_forest_node_t et_forest_parent PARAMS ((et_forest_t, et_forest_node_t)); |
| extern et_forest_node_t et_forest_common_ancestor PARAMS ((et_forest_t, |
| et_forest_node_t, |
| et_forest_node_t)); |
| extern void * et_forest_node_value PARAMS ((et_forest_t, et_forest_node_t)); |
| extern int et_forest_enumerate_sons PARAMS ((et_forest_t, et_forest_node_t, |
| et_forest_node_t *)); |
| |
| #ifdef __cplusplus |
| } |
| #endif /* __cplusplus */ |
| |
| #endif /* _ET_TREE_H */ |