192 lines
8.5 KiB
C
192 lines
8.5 KiB
C
/*************************************************************************/
|
|
/* */
|
|
/* Centre for Speech Technology Research */
|
|
/* University of Edinburgh, UK */
|
|
/* Copyright (c) 1998 */
|
|
/* All Rights Reserved. */
|
|
/* Permission is hereby granted, free of charge, to use and distribute */
|
|
/* this software and its documentation without restriction, including */
|
|
/* without limitation the rights to use, copy, modify, merge, publish, */
|
|
/* distribute, sublicense, and/or sell copies of this work, and to */
|
|
/* permit persons to whom this work is furnished to do so, subject to */
|
|
/* the following conditions: */
|
|
/* 1. The code must retain the above copyright notice, this list of */
|
|
/* conditions and the following disclaimer. */
|
|
/* 2. Any modifications must be clearly marked as such. */
|
|
/* 3. Original authors' names are not deleted. */
|
|
/* 4. The authors' names are not used to endorse or promote products */
|
|
/* derived from this software without specific prior written */
|
|
/* permission. */
|
|
/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
|
|
/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
|
|
/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
|
|
/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
|
|
/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
|
|
/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
|
|
/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
|
|
/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
|
|
/* THIS SOFTWARE. */
|
|
/* */
|
|
/*************************************************************************/
|
|
/* Author : Alan W Black */
|
|
/* Date : February 1998 */
|
|
/* --------------------------------------------------------------------- */
|
|
/* Functions for TREE relations */
|
|
/* */
|
|
/*************************************************************************/
|
|
#ifndef __EST_RELATION_TREE_H__
|
|
#define __EST_RELATION_TREE_H__
|
|
|
|
/**@name Functions for building and traversing tree relations
|
|
|
|
*/
|
|
//@{
|
|
|
|
/**@name Tree traversal functions
|
|
*/
|
|
|
|
//@{
|
|
|
|
/// return parent of <parameter>n</parameter>
|
|
inline EST_Item *parent(const EST_Item *n) { return n->first()->up(); }
|
|
|
|
/// return first daughter of <parameter>n</parameter>
|
|
inline EST_Item *daughter1(const EST_Item *n) { return n->down(); }
|
|
|
|
/// return second daughter of <parameter>n</parameter>
|
|
inline EST_Item *daughter2(const EST_Item *n) { return n->down()->next(); }
|
|
|
|
/// return nth daughter of <parameter>n</parameter>
|
|
EST_Item *daughtern(const EST_Item *n, int nth);
|
|
|
|
/// return last daughter of <parameter>n</parameter>
|
|
inline EST_Item *daughtern(const EST_Item *n) { return n->down()->last(); }
|
|
|
|
/// return next sibling (sister) of <parameter>n</parameter>
|
|
inline EST_Item *next_sibling(const EST_Item *n) { return n->next(); }
|
|
|
|
/// return previous sibling (sister) of <parameter>n</parameter>
|
|
inline EST_Item *prev_sibling(const EST_Item *n) { return n->prev(); }
|
|
|
|
/// return root node of treeprevious sibling (sister) of <parameter>n</parameter>
|
|
inline EST_Item *root(const EST_Item *n) { return n->top(); }
|
|
|
|
/** return parent of <parameter>n</parameter> as seen from relation
|
|
<parameter>relname</parameter> */
|
|
inline EST_Item *parent(const EST_Item *n,const char *relname)
|
|
{ return parent(as(n,relname)); }
|
|
|
|
//inline EST_Item *daughters(const EST_Item *n,const char *relname)
|
|
// { return daughters(as(n,relname)); }
|
|
|
|
/** return first daughter of <parameter>n</parameter> as seen from relation
|
|
<parameter>relname</parameter> */
|
|
inline EST_Item *daughter1(const EST_Item *n,const char *relname)
|
|
{ return daughter1(as(n,relname)); }
|
|
|
|
/** return second daughter of <parameter>n</parameter> as seen from relation
|
|
<parameter>relname</parameter> */
|
|
inline EST_Item *daughter2(const EST_Item *n,const char *relname)
|
|
{ return daughter2(as(n,relname)); }
|
|
|
|
/** return last daughter of <parameter>n</parameter> as seen from relation
|
|
<parameter>relname</parameter> */
|
|
inline EST_Item *daughtern(const EST_Item *n,const char *relname)
|
|
{ return daughtern(as(n,relname)); }
|
|
|
|
/** return next sibling (sister) of <parameter>n</parameter> as seen
|
|
from relation <parameter>relname</parameter> */
|
|
inline EST_Item *next_sibling(const EST_Item *n,const char *relname)
|
|
{ return next_sibling(as(n,relname)); }
|
|
|
|
/** return previous sibling (sister) of <parameter>n</parameter> as seen
|
|
from relation <parameter>relname</parameter> */
|
|
inline EST_Item *prev_sibling(const EST_Item *n,const char *relname)
|
|
{ return prev_sibling(as(n,relname)); }
|
|
|
|
/** return root of tree of <parameter>n</parameter> as seen from
|
|
relation <parameter>relname</parameter> */
|
|
inline EST_Item *root(const EST_Item *n,const char *relname)
|
|
{ return root(as(n,relname)); }
|
|
|
|
// should be deleted.
|
|
EST_Item *first_leaf_in_tree(const EST_Item *root);
|
|
|
|
// should be deleted.
|
|
EST_Item *last_leaf_in_tree(const EST_Item *root);
|
|
|
|
/** return the first leaf (terminal node) which is dominated by
|
|
<parameter>n</parameter>. Note that this is different from daughter1 etc
|
|
as this descends the tree to find the leftmost terminal node (it
|
|
is like the transitive closure of daughter1).
|
|
*/
|
|
inline EST_Item *first_leaf(const EST_Item *n) {return first_leaf_in_tree(n);}
|
|
|
|
/** return the last leaf (terminal node) which is dominated by
|
|
<parameter>n</parameter>. Note that this is different from daughter1 etc
|
|
as this descends the tree to find the right terminal node (it is
|
|
like the transitive closure of daughtern).
|
|
*/
|
|
inline EST_Item *last_leaf(const EST_Item *n) { return last_leaf_in_tree(n); }
|
|
|
|
/** Return next leaf in tree given <parameter>n</parameter>. If
|
|
<parameter>n</parameter> is a terminal node, next_leaf() will return
|
|
the next leaf in the tree. If <parameter>n</parameter> is not
|
|
terminal, this will return the leftmost terminal node dominated by
|
|
<parameter>n</parameter>. This will return 0 only when the last leaf in
|
|
the relation has been passed.
|
|
*/
|
|
inline EST_Item *next_leaf(const EST_Item *n) { return n->next_leaf(); }
|
|
|
|
/** Return number of leaves (terminal nodes) under <parameter>n</parameter>
|
|
*/
|
|
int num_leaves(const EST_Item *n);
|
|
|
|
/** Given a node <parameter>t</parameter>, return true if
|
|
<parameter>c</parameter> is under it in a tree */
|
|
int in_tree(const EST_Item *c,const EST_Item *t);
|
|
|
|
//@}
|
|
|
|
/**@name Tree building functions */
|
|
//@{
|
|
|
|
/** Add a daughter to node <parameter>n</parameter>, after any
|
|
existing daughters, and return the next daughter. If
|
|
<parameter>p</parameter> is 0, make a new node for the daughter,
|
|
otherwise add <parameter>p</parameter> to this relation as
|
|
<parameter>n</parameter>'s daughter. */
|
|
|
|
EST_Item *append_daughter(EST_Item *n, EST_Item *p=0);
|
|
|
|
/** Add a daughter to node <parameter>n</parameter> as seen from
|
|
relation <parameter>relname</parameter>, after any existing
|
|
daughters, and return the next daughter. If <parameter>p</parameter>
|
|
is 0, make a new node for the daughter, otherwise add
|
|
<parameter>p</parameter> to this relation as
|
|
<parameter>n</parameter>'s daughter. */
|
|
|
|
EST_Item *append_daughter(EST_Item *n, const char *relname, EST_Item *p=0);
|
|
|
|
/** Add a daughter to node <parameter>n</parameter>, before any
|
|
existing daughters, and return the next daughter. If
|
|
<parameter>p</parameter> is 0, make a new node for the daughter,
|
|
otherwise add <parameter>p</parameter> to this relation as
|
|
<parameter>n</parameter>'s daughter. */
|
|
|
|
EST_Item *prepend_daughter(EST_Item *n, EST_Item *p=0);
|
|
|
|
/** Add a daughter to node <parameter>n</parameter> as seen from
|
|
relation <parameter>relname</parameter>, before any existing
|
|
daughters, and return the next daughter. If <parameter>p</parameter>
|
|
is 0, make a new node for the daughter, otherwise add
|
|
<parameter>p</parameter> to this relation as
|
|
<parameter>n</parameter>'s daughter. */
|
|
|
|
EST_Item *prepend_daughter(EST_Item *n, const char *relname, EST_Item *p=0);
|
|
|
|
//@}
|
|
|
|
//@}
|
|
#endif
|