Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_Relation_tree.h
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1998 */
6 /* All Rights Reserved. */
7 /* Permission is hereby granted, free of charge, to use and distribute */
8 /* this software and its documentation without restriction, including */
9 /* without limitation the rights to use, copy, modify, merge, publish, */
10 /* distribute, sublicense, and/or sell copies of this work, and to */
11 /* permit persons to whom this work is furnished to do so, subject to */
12 /* the following conditions: */
13 /* 1. The code must retain the above copyright notice, this list of */
14 /* conditions and the following disclaimer. */
15 /* 2. Any modifications must be clearly marked as such. */
16 /* 3. Original authors' names are not deleted. */
17 /* 4. The authors' names are not used to endorse or promote products */
18 /* derived from this software without specific prior written */
19 /* permission. */
20 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
21 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
22 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
23 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
24 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
25 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
26 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
27 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
28 /* THIS SOFTWARE. */
29 /* */
30 /*************************************************************************/
31 /* Author : Alan W Black */
32 /* Date : February 1998 */
33 /* --------------------------------------------------------------------- */
34 /* Functions for TREE relations */
35 /* */
36 /*************************************************************************/
37 #ifndef __EST_RELATION_TREE_H__
38 #define __EST_RELATION_TREE_H__
39 
40 /**@name Functions for building and traversing tree relations
41 
42  */
43 //@{
44 
45 /**@name Tree traversal functions
46 */
47 
48 //@{
49 
50 /// return parent of <parameter>n</parameter>
51 inline EST_Item *parent(const EST_Item *n) { return n->first()->up(); }
52 
53 /// return first daughter of <parameter>n</parameter>
54 inline EST_Item *daughter1(const EST_Item *n) { return n->down(); }
55 
56 /// return second daughter of <parameter>n</parameter>
57 inline EST_Item *daughter2(const EST_Item *n) { return n->down()->next(); }
58 
59 /// return nth daughter of <parameter>n</parameter>
60 EST_Item *daughtern(const EST_Item *n, int nth);
61 
62 /// return last daughter of <parameter>n</parameter>
63 inline EST_Item *daughtern(const EST_Item *n) { return n->down()->last(); }
64 
65 /// return next sibling (sister) of <parameter>n</parameter>
66 inline EST_Item *next_sibling(const EST_Item *n) { return n->next(); }
67 
68 /// return previous sibling (sister) of <parameter>n</parameter>
69 inline EST_Item *prev_sibling(const EST_Item *n) { return n->prev(); }
70 
71 /// return root node of treeprevious sibling (sister) of <parameter>n</parameter>
72 inline EST_Item *root(const EST_Item *n) { return n->top(); }
73 
74 /** return parent of <parameter>n</parameter> as seen from relation
75 <parameter>relname</parameter> */
76 inline EST_Item *parent(const EST_Item *n,const char *relname)
77  { return parent(as(n,relname)); }
78 
79 //inline EST_Item *daughters(const EST_Item *n,const char *relname)
80 // { return daughters(as(n,relname)); }
81 
82 /** return first daughter of <parameter>n</parameter> as seen from relation
83  <parameter>relname</parameter> */
84 inline EST_Item *daughter1(const EST_Item *n,const char *relname)
85  { return daughter1(as(n,relname)); }
86 
87 /** return second daughter of <parameter>n</parameter> as seen from relation
88  <parameter>relname</parameter> */
89 inline EST_Item *daughter2(const EST_Item *n,const char *relname)
90  { return daughter2(as(n,relname)); }
91 
92 /** return last daughter of <parameter>n</parameter> as seen from relation
93  <parameter>relname</parameter> */
94 inline EST_Item *daughtern(const EST_Item *n,const char *relname)
95  { return daughtern(as(n,relname)); }
96 
97 /** return next sibling (sister) of <parameter>n</parameter> as seen
98  from relation <parameter>relname</parameter> */
99 inline EST_Item *next_sibling(const EST_Item *n,const char *relname)
100  { return next_sibling(as(n,relname)); }
101 
102 /** return previous sibling (sister) of <parameter>n</parameter> as seen
103  from relation <parameter>relname</parameter> */
104 inline EST_Item *prev_sibling(const EST_Item *n,const char *relname)
105  { return prev_sibling(as(n,relname)); }
106 
107 /** return root of tree of <parameter>n</parameter> as seen from
108  relation <parameter>relname</parameter> */
109 inline EST_Item *root(const EST_Item *n,const char *relname)
110  { return root(as(n,relname)); }
111 
112 // should be deleted.
113 EST_Item *first_leaf_in_tree(const EST_Item *root);
114 
115 // should be deleted.
116 EST_Item *last_leaf_in_tree(const EST_Item *root);
117 
118 /** return the first leaf (terminal node) which is dominated by
119  <parameter>n</parameter>. Note that this is different from daughter1 etc
120 as this descends the tree to find the leftmost terminal node (it
121 is like the transitive closure of daughter1).
122 */
123 inline EST_Item *first_leaf(const EST_Item *n) {return first_leaf_in_tree(n);}
124 
125 /** return the last leaf (terminal node) which is dominated by
126  <parameter>n</parameter>. Note that this is different from daughter1 etc
127 as this descends the tree to find the right terminal node (it is
128 like the transitive closure of daughtern).
129 */
130 inline EST_Item *last_leaf(const EST_Item *n) { return last_leaf_in_tree(n); }
131 
132 /** Return next leaf in tree given <parameter>n</parameter>. If
133 <parameter>n</parameter> is a terminal node, next_leaf() will return
134 the next leaf in the tree. If <parameter>n</parameter> is not
135 terminal, this will return the leftmost terminal node dominated by
136 <parameter>n</parameter>. This will return 0 only when the last leaf in
137 the relation has been passed.
138 */
139 inline EST_Item *next_leaf(const EST_Item *n) { return n->next_leaf(); }
140 
141 /** Return number of leaves (terminal nodes) under <parameter>n</parameter>
142  */
143 int num_leaves(const EST_Item *n);
144 
145 /** Given a node <parameter>t</parameter>, return true if
146  <parameter>c</parameter> is under it in a tree */
147 int in_tree(const EST_Item *c,const EST_Item *t);
148 
149 //@}
150 
151 /**@name Tree building functions */
152 //@{
153 
154 /** Add a daughter to node <parameter>n</parameter>, after any
155 existing daughters, and return the next daughter. If
156 <parameter>p</parameter> is 0, make a new node for the daughter,
157 otherwise add <parameter>p</parameter> to this relation as
158 <parameter>n</parameter>'s daughter. */
159 
160 EST_Item *append_daughter(EST_Item *n, EST_Item *p=0);
161 
162 /** Add a daughter to node <parameter>n</parameter> as seen from
163 relation <parameter>relname</parameter>, after any existing
164 daughters, and return the next daughter. If <parameter>p</parameter>
165 is 0, make a new node for the daughter, otherwise add
166 <parameter>p</parameter> to this relation as
167 <parameter>n</parameter>'s daughter. */
168 
169 EST_Item *append_daughter(EST_Item *n, const char *relname, EST_Item *p=0);
170 
171 /** Add a daughter to node <parameter>n</parameter>, before any
172 existing daughters, and return the next daughter. If
173 <parameter>p</parameter> is 0, make a new node for the daughter,
174 otherwise add <parameter>p</parameter> to this relation as
175 <parameter>n</parameter>'s daughter. */
176 
177 EST_Item *prepend_daughter(EST_Item *n, EST_Item *p=0);
178 
179 /** Add a daughter to node <parameter>n</parameter> as seen from
180 relation <parameter>relname</parameter>, before any existing
181 daughters, and return the next daughter. If <parameter>p</parameter>
182 is 0, make a new node for the daughter, otherwise add
183 <parameter>p</parameter> to this relation as
184 <parameter>n</parameter>'s daughter. */
185 
186 EST_Item *prepend_daughter(EST_Item *n, const char *relname, EST_Item *p=0);
187 
188 //@}
189 
190 //@}
191 #endif