1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1998 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /*************************************************************************/
33 /* Author : Alan W Black */
34 /* Date : May 1998 */
35 /*-----------------------------------------------------------------------*/
36 /* Linguistic items (e.g. words, phones etc) held as part of Relations */
37 /* */
38 /* These objects may be held in relations within an utterance. They */
39 /* fact contain two sections, a structural part and a contents part */
40 /* (EST_Item_Content) though the user will usually only see the whole */
41 /* object. The content part may be shared between linguistic items in */
42 /* other relations, e.g. the word item may appear both in the word */
43 /* relation and the syntax relation. */
44 /* */
45 /* Each linguistic item is in a particular relation but it is easy */
46 /* to link to that item in another relation. Traversal of the relation */
47 /* for an item in it is trivial. */
48 /* */
49 /*=======================================================================*/
50 #include <cstdlib>
51 #include <cstdio>
52 #include <iostream>
53 #include <fstream>
54 #include "ling_class/EST_Item.h"
55 #include "ling_class/EST_Relation.h"
56 #include "ling_class/EST_Utterance.h"
57 #include "EST_TKVL.h"
58 #include "EST_UList.h"
59 #include "EST_string_aux.h"
60
61 #include "ling_class_init.h"
62
63 /* Class initialisation. This is where you should register
64 * feature functions and so on.
65 */
class_init(void)66 void EST_Item::class_init(void)
67 {
68 #ifdef EST_DEBUGGING
69 cerr << "Calling EST_Item init\n";
70 #endif
71
72 ling_class_init::use();
73
74 EST_register_feature_functions(standard);
75
76 #ifdef EST_DEBUGGING
77 cerr << "Finished EST_Item init\n";
78 #endif
79 }
80
EST_Item()81 EST_Item::EST_Item()
82 {
83 p_relation = 0;
84 p_contents = 0;
85 n=p=u=d=0;
86 set_contents(0);
87 }
88
copy(const EST_Item & s)89 void EST_Item::copy(const EST_Item &s)
90 {
91 // You can't really do this in general as a node is doubly
92 // linked to its neighbours and item. Copying all the fields would
93 // mean it was no longer true (unless you copied everything).
94 // So all you get for this is a *copy* of the contents (not a reference
95 // to)
96 p_relation = 0;
97 p_contents = 0;
98 n=p=u=d=0;
99 set_contents(0); // get an empty contents structure
100 *p_contents = *s.p_contents;
101 }
102
EST_Item(const EST_Item & i)103 EST_Item::EST_Item(const EST_Item &i)
104 {
105 copy(i);
106 }
107
~EST_Item()108 EST_Item::~EST_Item()
109 {
110 // Delete this item and its daughters (and the contents with no
111 // other links)
112 // Assumes a tree structure
113 EST_Item *ds,*nds;
114
115 // Tidy up pointers to this
116 if (n != 0)
117 {
118 n->p = p;
119 n->u = u; // when deleting first daughter.
120 }
121 if (p != 0) p->n = n;
122 if (u != 0) u->d = n;
123
124 if (p_relation)
125 {
126 if (p_relation->p_head == this)
127 p_relation->p_head = n;
128 if (p_relation->p_tail == this)
129 p_relation->p_tail = p;
130 }
131
132 // A little cleverer with the daughters
133 for (ds=d; ds != 0; ds=nds)
134 {
135 nds=ds->n;
136 delete ds;
137 }
138
139 unref_contents();
140 }
141
EST_Item(EST_Relation * rel)142 EST_Item::EST_Item(EST_Relation *rel)
143 {
144 p_relation = rel;
145 p_contents = 0;
146 n=p=u=d=0;
147 }
148
149 // all internal ids are found by getting the next id number from
150 // the utterance and prefixing a "_" to show that this is internally
151 // generated.
assign_id(EST_Item * s)152 static void assign_id(EST_Item *s)
153 {
154 if (s->f_present("id"))
155 return;
156
157 EST_Utterance *u = get_utt(s);
158 if (u != 0)
159 s->set("id", "_" + itoString(u->next_id()));
160 }
161
EST_Item(EST_Relation * rel,EST_Item * li)162 EST_Item::EST_Item(EST_Relation *rel, EST_Item *li)
163 {
164 p_relation = rel;
165 p_contents = 0;
166 n=p=u=d=0;
167 set_contents(li->contents());
168
169 assign_id(this);
170 }
171
evaluate_features()172 void EST_Item::evaluate_features()
173 {
174 evaluate(this,p_contents->f);
175 }
176
unref_contents()177 void EST_Item::unref_contents()
178 {
179 // Unref the related contents to this item, delete if no-one else is
180 // referencing it
181 if (p_contents != 0)
182 {
183 if (p_contents->unref_relation(relation_name()))
184 delete p_contents;
185 p_contents = 0;
186 }
187 }
188
unref_all()189 void EST_Item::unref_all()
190 {
191 // Unreference this item from all its relations, deleting its contents
192
193 p_contents->unref_and_delete();
194 }
195
relation_name() const196 const EST_String &EST_Item::relation_name() const
197 {
198 return ((this == 0) || (p_relation == 0)) ?
199 EST_String::Empty : p_relation->name();
200 }
201
set_contents(EST_Item_Content * new_contents)202 void EST_Item::set_contents(EST_Item_Content *new_contents)
203 {
204 // This function is for internal use only, general use of this
205 // is likely to be unsafe.
206 EST_Item_Content *c;
207 if (new_contents == 0)
208 c = new EST_Item_Content;
209 else
210 c = new_contents;
211
212 if (p_contents != c)
213 {
214 unref_contents();
215 p_contents = c;
216
217 EST_Item *nn_item = p_contents->Relation(relation_name());
218 if (nn_item) // this is already linked to this relation
219 { // can't recurse on set_contents
220 nn_item->p_contents = new EST_Item_Content;
221 nn_item->p_contents->relations.add_item(relation_name(),
222 est_val(nn_item));
223 }
224 p_contents->relations.add_item(relation_name(),est_val(this));
225 }
226 }
227
length() const228 int EST_Item::length() const
229 {
230 int i=0;
231 EST_Item *nn = (EST_Item *)(void *)this;
232 for (; nn; nn=nn->n,i++);
233 return i;
234 }
235
insert_after(EST_Item * si)236 EST_Item *EST_Item::insert_after(EST_Item *si)
237 {
238 // Create a new item and add it after t, and return it.
239 // Include the cross link from this new item's contents to si, and
240 // from si's relations fields back to the new node
241 EST_Item *new_node = new EST_Item(p_relation,si);
242
243 new_node->p = this;
244 new_node->n = this->n;
245 if (new_node->n != 0)
246 new_node->n->p = new_node;
247 this->n = new_node;
248
249 if (p_relation && (p_relation->p_tail == this))
250 p_relation->p_tail = new_node;
251
252 return new_node;
253 }
254
insert_before(EST_Item * si)255 EST_Item *EST_Item::insert_before(EST_Item *si)
256 {
257 // Create a new node and add it before this, and return it.
258 EST_Item *new_node = new EST_Item(p_relation,si);
259
260 new_node->n = this;
261 new_node->p = this->p;
262 if (new_node->p != 0)
263 new_node->p->n = new_node;
264 this->p = new_node;
265 // This makes an assumption that we represent trees with only
266 // the first daughter pointing to the parent
267 if (this->u)
268 {
269 new_node->u = this->u;
270 new_node->u->d = new_node;
271 this->u = 0;
272 }
273
274 if (p_relation && (p_relation->p_head == this))
275 p_relation->p_head = new_node;
276
277 return new_node;
278 }
279
insert_below(EST_Item * si)280 EST_Item *EST_Item::insert_below(EST_Item *si)
281 {
282 // Create a new node and add it below this, and return it.
283 EST_Item *new_node = new EST_Item(p_relation,si);
284
285 new_node->u = this;
286 new_node->d = this->d;
287 if (new_node->d != 0)
288 new_node->d->u = new_node;
289 this->d = new_node;
290
291 return new_node;
292 }
293
insert_above(EST_Item * si)294 EST_Item *EST_Item::insert_above(EST_Item *si)
295 {
296 // Create a new node and add it above this, and return it.
297 EST_Item *new_node = new EST_Item(p_relation,si);
298
299 new_node->d = this;
300 new_node->u = this->u;
301 if (new_node->u != 0)
302 new_node->u->d = new_node;
303 this->u = new_node;
304
305 if (p_relation && (p_relation->p_head == this))
306 p_relation->p_head = new_node;
307 if (p_relation && (p_relation->p_tail == this))
308 p_relation->p_tail = new_node;
309
310 return new_node;
311 }
312
insert_parent(EST_Item * si)313 EST_Item *EST_Item::insert_parent(EST_Item *si)
314 {
315 // Insert new parent here, by added a new below node and moving
316 // the contents down to it.
317 if (this == 0) return 0;
318
319 insert_below(0);
320 down()->set_contents(grab_contents());
321 if (si != 0)
322 set_contents(si->grab_contents());
323 else
324 set_contents(0);
325
326 return this;
327 }
328
last() const329 EST_Item *EST_Item::last() const
330 {
331 // To get round the const access to this
332 EST_Item *node = (EST_Item *)(void *)this;
333
334 if (this == 0) return 0;
335 for (; node->n != 0; node=node->n);
336 return node;
337 }
338
first() const339 EST_Item *EST_Item::first() const
340 {
341 // To get round the const access to this
342 EST_Item *node = (EST_Item *)(void *)this;
343
344 if (this == 0) return 0;
345 for (; node->p != 0; node=node->p);
346 return node;
347 }
348
top() const349 EST_Item *EST_Item::top() const
350 {
351 EST_Item *node = (EST_Item *)(void *)this;
352
353 if (this == 0) return 0;
354 for (; parent(node) != 0; node=parent(node));
355 return node;
356 }
357
next_leaf() const358 EST_Item *EST_Item::next_leaf() const
359 {
360 if (this == 0)
361 return 0;
362 else if (next() != 0)
363 return next()->first_leaf();
364 else
365 return parent(this)->next_leaf();
366 }
367
next_item() const368 EST_Item *EST_Item::next_item() const
369 {
370 // For traversal through a relation, in pre-order (root then daughters)
371 if (this == 0)
372 return 0;
373 else if (down() != 0)
374 return down();
375 else if (next() != 0)
376 return next();
377 else
378 { // at the right most leaf so go up until you find a parent with a next
379 for (EST_Item *pp = parent(this); pp != 0; pp = parent(pp))
380 if (pp->next())
381 return pp->next();
382 return 0;
383 }
384 }
385
first_leaf() const386 EST_Item *EST_Item::first_leaf() const
387 {
388 // Leafs are defined as those nodes with no daughters
389 if (this == 0)
390 return 0;
391 if (down() == 0)
392 return (EST_Item *)(void *)this;
393 else
394 return down()->first_leaf();
395 }
396
last_leaf() const397 EST_Item *EST_Item::last_leaf() const
398 {
399 // Leafs are defined as those nodes with no daughters
400 if (this == 0)
401 return 0;
402 else if (next())
403 return next()->last_leaf();
404 else if (down())
405 return down()->last_leaf();
406 else
407 return (EST_Item *)(void *)this;
408 }
409
first_leaf_in_tree(const EST_Item * root)410 EST_Item *first_leaf_in_tree(const EST_Item *root)
411 {
412 return root->first_leaf();
413 }
414
last_leaf_in_tree(const EST_Item * root)415 EST_Item *last_leaf_in_tree(const EST_Item *root)
416 {
417 if (root == 0)
418 return 0;
419 else if (root->down() == 0)
420 return (EST_Item *)(void *)root;
421 else
422 return root->down()->last_leaf();
423 }
424
append_daughter(EST_Item * si)425 EST_Item *EST_Item::append_daughter(EST_Item *si)
426 {
427 if (this == 0)
428 return 0;
429 EST_Item *nnode;
430 EST_Item *its_downs;
431
432 // Because we don't distinguish forests properly we need
433 // to do nasty things if this si is already associated to a
434 // this relation and its "in the top list"
435 EST_Item *c = si->as_relation(relation_name());
436 if (in_list(c,p_relation->head()))
437 {
438 // need to save its daughters to put on the new node
439 its_downs = c->d;
440 c->d = 0; // otherwise it could delete its sub tree
441 if (its_downs) its_downs->u = 0;
442
443 if (down() == 0)
444 nnode = insert_below(si);
445 else
446 nnode = down()->last()->insert_after(si);
447 // put daughters back on the new item
448 if (its_downs)
449 {
450 its_downs->u = nnode;
451 nnode->d = its_downs;
452 }
453
454 delete c; // delete its old form from the top level
455 }
456 else if (down() == 0)
457 nnode = insert_below(si);
458 else
459 nnode = down()->last()->insert_after(si);
460
461 return nnode;
462 }
463
prepend_daughter(EST_Item * si)464 EST_Item *EST_Item::prepend_daughter(EST_Item *si)
465 {
466 if (this == 0)
467 return 0;
468 EST_Item *nnode;
469 EST_Item *its_downs;
470
471 // Because we don't distinguish forests properly we need
472 // to do nasty things if this si is already associated to a
473 // this relation and its "in the top list"
474 EST_Item *c = si->as_relation(relation_name());
475 if (in_list(c,p_relation->head()))
476 {
477 // need to save its daughters to put on the new node
478 its_downs = c->d;
479 c->d = 0; // otherwise it could delete its sub tree
480 if (its_downs) its_downs->u = 0;
481
482 if (down() == 0)
483 nnode = insert_below(si);
484 else
485 nnode = down()->insert_before(si);
486 // put daughters back on the new item
487 if (its_downs)
488 {
489 its_downs->u = nnode;
490 nnode->d = its_downs;
491 }
492
493 delete c; // delete its old form from the top level
494 }
495 else if (down() == 0)
496 nnode = insert_below(si);
497 else
498 nnode = down()->insert_before(si);
499
500 return nnode;
501 }
502
grab_daughters()503 EST_Item *EST_Item::grab_daughters()
504 {
505 EST_Item *dd = down();
506 if (dd)
507 {
508 dd->u = 0;
509 d = 0;
510 }
511 return dd;
512 }
513
grab_contents(void)514 EST_Item_Content *EST_Item::grab_contents(void)
515 {
516 // Unreference contents, but don't delete them if that's the
517 // last reference. It is the caller's responsibility to deal
518 // with these contents, typically they are just about to be set
519 // as contents of someone else so are only orphaned for a short
520 // time
521 EST_Item_Content *c = contents();
522 c->unref_relation(relation_name());
523 p_contents = 0;
524 set_contents(0); // can't sit without contents
525 return c;
526 }
527
copy_node_tree(EST_Item * from,EST_Item * to)528 void copy_node_tree(EST_Item *from, EST_Item *to)
529 {
530 // Copy this node and all its siblings and daughters
531
532 if (from->next() != 0)
533 copy_node_tree(from->next(),to->insert_after(from->next()));
534
535 if (from->down() != 0)
536 copy_node_tree(from->down(),to->insert_below(from->down()));
537
538 }
539
copy_node_tree_contents(EST_Item * from,EST_Item * to)540 void copy_node_tree_contents(EST_Item *from, EST_Item *to)
541 {
542 // Copy this node and all its siblings and daughters
543 // also copy the item's contents
544
545 if (from->next() != 0)
546 {
547 EST_Item i = *from->next(); // copies the contents
548 copy_node_tree_contents(from->next(),to->insert_after(&i));
549 }
550
551 if (from->down() != 0)
552 {
553 EST_Item i = *from->down();
554 copy_node_tree_contents(from->down(),to->insert_below(&i));
555 }
556
557 }
558
verify() const559 int EST_Item::verify() const
560 {
561 // Return FALSE if this node and its neighbours aren't
562 // properly linked
563
564 if (this == 0)
565 return TRUE;
566 if (((d == 0) || (d->u == this)) &&
567 ((n == 0) || (n->p == this)) &&
568 (d->verify()) &&
569 (n->verify()))
570 return TRUE;
571 else
572 return FALSE;
573 }
574
append_daughter(EST_Item * n,EST_Item * p)575 EST_Item *append_daughter(EST_Item *n, EST_Item *p)
576 {
577 return n->append_daughter(p);
578 }
579
append_daughter(EST_Item * n,const char * relname,EST_Item * p)580 EST_Item *append_daughter(EST_Item *n,const char *relname, EST_Item *p)
581 {
582 return append_daughter(as(n,relname),p);
583 }
584
prepend_daughter(EST_Item * n,EST_Item * p)585 EST_Item *prepend_daughter(EST_Item *n, EST_Item *p)
586 {
587 return n->prepend_daughter(p);
588 }
589
prepend_daughter(EST_Item * n,const char * relname,EST_Item * p)590 EST_Item *prepend_daughter(EST_Item *n, const char *relname, EST_Item *p)
591 {
592 return prepend_daughter(as(n,relname),p);
593 }
594
remove_item(EST_Item * l,const char * relname)595 void remove_item(EST_Item *l, const char *relname)
596 {
597 EST_Item *lr = l->as_relation(relname);
598 EST_Relation *r = lr->relation();
599
600 if ((lr != 0) && (r != 0))
601 r->remove_item(lr);
602 }
603
operator =(const EST_Item & s)604 EST_Item &EST_Item::operator=(const EST_Item &s)
605 {
606 copy(s);
607 return *this;
608 }
609
operator <<(ostream & s,const EST_Item & a)610 ostream& operator << (ostream &s, const EST_Item &a)
611 {
612 a.features().save(s);
613 return s;
614 }
615
616
evaluate(EST_Item * a,EST_Features & f)617 void evaluate(EST_Item *a,EST_Features &f)
618 {
619 EST_Features::RwEntries p;
620
621 for(p.begin(f); p; ++p)
622 if (p->v.type() == val_type_featfunc)
623 {
624 if (featfunc(p->v) != NULL)
625 p->v = (featfunc(p->v))(a);
626 else
627 {
628 fprintf(stderr, "NULL %s function\n", (const char *) p->k );
629 p->v = EST_Features::feature_default_value;
630 }
631 }
632 }
633
634 VAL_REGISTER_CLASS_NODEL(item,EST_Item)
635