]>
Commit | Line | Data |
---|---|---|
f1cfb09f JH |
1 | /* Et-forest data structure implementation. |
2 | Copyright (C) 2002 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 2 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; if not, write to the Free Software | |
16 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
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 | |
fbe5a4a6 | 21 | poly-logarithmic time for nearest common ancestor. |
f1cfb09f JH |
22 | |
23 | ET tree strores its structue 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 sligtly 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 | #include <ansidecl.h> | |
52 | #include <stddef.h> | |
53 | ||
54 | #ifdef __cplusplus | |
55 | extern "C" { | |
56 | #endif /* __cplusplus */ | |
57 | ||
58 | typedef struct et_forest *et_forest_t; | |
59 | typedef struct et_forest_node *et_forest_node_t; | |
60 | ||
61 | extern et_forest_t et_forest_create PARAMS ((void)); | |
62 | ||
63 | extern void et_forest_delete PARAMS ((et_forest_t)); | |
64 | ||
65 | extern et_forest_node_t et_forest_add_node PARAMS ((et_forest_t, void *)); | |
66 | extern int et_forest_add_edge PARAMS ((et_forest_t, et_forest_node_t, | |
67 | et_forest_node_t)); | |
68 | extern void et_forest_remove_node PARAMS ((et_forest_t, et_forest_node_t)); | |
69 | extern int et_forest_remove_edge PARAMS ((et_forest_t, et_forest_node_t, | |
70 | et_forest_node_t)); | |
71 | extern et_forest_node_t et_forest_parent PARAMS ((et_forest_t, et_forest_node_t)); | |
72 | extern et_forest_node_t et_forest_common_ancestor PARAMS ((et_forest_t, | |
73 | et_forest_node_t, | |
74 | et_forest_node_t)); | |
75 | extern void * et_forest_node_value PARAMS ((et_forest_t, et_forest_node_t)); | |
76 | extern int et_forest_enumerate_sons PARAMS ((et_forest_t, et_forest_node_t, | |
77 | et_forest_node_t *)); | |
78 | ||
79 | #ifdef __cplusplus | |
80 | } | |
81 | #endif /* __cplusplus */ | |
82 | ||
83 | #endif /* _ET_TREE_H */ |