00001 /* Et-forest data structure implementation. 00002 Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. 00003 00004 This program is free software; you can redistribute it and/or modify 00005 it under the terms of the GNU General Public License as published by 00006 the Free Software Foundation; either version 2 of the License, or 00007 (at your option) any later version. 00008 00009 This program is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 GNU General Public License for more details. 00013 00014 You should have received a copy of the GNU General Public License 00015 along with this program; if not, write to the Free Software 00016 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 00017 00018 /* This package implements ET forest data structure. Each tree in 00019 the structure maintains a tree structure and offers logarithmic time 00020 for tree operations (insertion and removal of nodes and edges) and 00021 poly-logarithmic time for nearest common ancestor. 00022 00023 ET tree stores its structure as a sequence of symbols obtained 00024 by dfs(root) 00025 00026 dfs (node) 00027 { 00028 s = node; 00029 for each child c of node do 00030 s = concat (s, c, node); 00031 return s; 00032 } 00033 00034 For example for tree 00035 00036 1 00037 / | \ 00038 2 3 4 00039 / | 00040 4 5 00041 00042 the sequence is 1 2 4 2 5 3 1 3 1 4 1. 00043 00044 The sequence is stored in a slightly modified splay tree. 00045 In order to support various types of node values, a hashtable 00046 is used to convert node values to the internal representation. */ 00047 00048 #ifndef _ET_TREE_H 00049 #define _ET_TREE_H 00050 00051 #include <ansidecl.h> 00052 #include <stddef.h> 00053 00054 #ifdef __cplusplus 00055 extern "C" { 00056 #endif /* __cplusplus */ 00057 00058 /* The node representing the node in an et tree. */ 00059 struct et_node 00060 { 00061 void *data; /* The data represented by the node. */ 00062 00063 int dfs_num_in, dfs_num_out; /* Number of the node in the dfs ordering. */ 00064 00065 struct et_node *father; /* Father of the node. */ 00066 struct et_node *son; /* The first of the sons of the node. */ 00067 struct et_node *left; 00068 struct et_node *right; /* The brothers of the node. */ 00069 00070 struct et_occ *rightmost_occ; /* The rightmost occurrence. */ 00071 struct et_occ *parent_occ; /* The occurrence of the parent node. */ 00072 }; 00073 00074 struct et_node *et_new_tree (void *data); 00075 void et_free_tree (struct et_node *); 00076 void et_set_father (struct et_node *, struct et_node *); 00077 void et_split (struct et_node *); 00078 struct et_node *et_nca (struct et_node *, struct et_node *); 00079 bool et_below (struct et_node *, struct et_node *); 00080 00081 #ifdef __cplusplus 00082 } 00083 #endif /* __cplusplus */ 00084 00085 #endif /* _ET_TREE_H */
1.5.6