Mercurial > hg > CbC > CbC_gcc
annotate gcc/et-forest.h @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | a06113de4d67 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Et-forest data structure implementation. |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2010 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Free Software Foundation, Inc. |
| 0 | 4 |
| 5 This program is free software; you can redistribute it and/or modify | |
| 6 it under the terms of the GNU General Public License as published by | |
| 7 the Free Software Foundation; either version 3 of the License, or | |
| 8 (at your option) any later version. | |
| 9 | |
| 10 This program is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 13 GNU General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU General Public License | |
| 16 along with this program; see the file COPYING3. If not see | |
| 17 <http://www.gnu.org/licenses/>. */ | |
| 18 | |
| 19 /* This package implements ET forest data structure. Each tree in | |
| 20 the structure maintains a tree structure and offers logarithmic time | |
| 21 for tree operations (insertion and removal of nodes and edges) and | |
| 22 poly-logarithmic time for nearest common ancestor. | |
| 23 | |
| 24 ET tree stores its structure as a sequence of symbols obtained | |
| 25 by dfs(root) | |
| 26 | |
| 27 dfs (node) | |
| 28 { | |
| 29 s = node; | |
| 30 for each child c of node do | |
| 31 s = concat (s, c, node); | |
| 32 return s; | |
| 33 } | |
| 34 | |
| 35 For example for tree | |
| 36 | |
| 37 1 | |
| 38 / | \ | |
| 39 2 3 4 | |
| 40 / | | |
| 41 4 5 | |
| 42 | |
| 43 the sequence is 1 2 4 2 5 3 1 3 1 4 1. | |
| 44 | |
| 45 The sequence is stored in a slightly modified splay tree. | |
| 46 In order to support various types of node values, a hashtable | |
| 47 is used to convert node values to the internal representation. */ | |
| 48 | |
| 49 #ifndef _ET_TREE_H | |
| 50 #define _ET_TREE_H | |
| 51 | |
| 52 #ifdef __cplusplus | |
| 53 extern "C" { | |
| 54 #endif /* __cplusplus */ | |
| 55 | |
| 56 /* The node representing the node in an et tree. */ | |
| 57 struct et_node | |
| 58 { | |
| 59 void *data; /* The data represented by the node. */ | |
| 60 | |
| 61 int dfs_num_in, dfs_num_out; /* Number of the node in the dfs ordering. */ | |
| 62 | |
| 63 struct et_node *father; /* Father of the node. */ | |
| 64 struct et_node *son; /* The first of the sons of the node. */ | |
| 65 struct et_node *left; | |
| 66 struct et_node *right; /* The brothers of the node. */ | |
| 67 | |
| 68 struct et_occ *rightmost_occ; /* The rightmost occurrence. */ | |
| 69 struct et_occ *parent_occ; /* The occurrence of the parent node. */ | |
| 70 }; | |
| 71 | |
| 72 struct et_node *et_new_tree (void *data); | |
| 73 void et_free_tree (struct et_node *); | |
| 74 void et_free_tree_force (struct et_node *); | |
| 75 void et_free_pools (void); | |
| 76 void et_set_father (struct et_node *, struct et_node *); | |
| 77 void et_split (struct et_node *); | |
| 78 struct et_node *et_nca (struct et_node *, struct et_node *); | |
| 79 bool et_below (struct et_node *, struct et_node *); | |
| 80 struct et_node *et_root (struct et_node *); | |
| 81 | |
| 82 #ifdef __cplusplus | |
| 83 } | |
| 84 #endif /* __cplusplus */ | |
| 85 | |
| 86 #endif /* _ET_TREE_H */ |