Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_Item.cc
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  */
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 
82 {
83  p_relation = 0;
84  p_contents = 0;
85  n=p=u=d=0;
86  set_contents(0);
87 }
88 
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 
104 {
105  copy(i);
106 }
107 
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 
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.
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 
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 
173 {
174  evaluate(this,p_contents->f);
175 }
176 
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 
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 
197 {
198  return ((this == 0) || (p_relation == 0)) ?
199  EST_String::Empty : p_relation->name();
200 }
201 
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 
228 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 
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 
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 
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 
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 
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 
329 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 
339 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 
349 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 
358 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 
368 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 
386 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 
397 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 
410 EST_Item *first_leaf_in_tree(const EST_Item *root)
411 {
412  return root->first_leaf();
413 }
414 
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 
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 
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 
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 
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 
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 
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 
559 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 
575 EST_Item *append_daughter(EST_Item *n, EST_Item *p)
576 {
577  return n->append_daughter(p);
578 }
579 
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 
585 EST_Item *prepend_daughter(EST_Item *n, EST_Item *p)
586 {
587  return n->prepend_daughter(p);
588 }
589 
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 
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 
604 EST_Item &EST_Item::operator=(const EST_Item &s)
605 {
606  copy(s);
607  return *this;
608 }
609 
610 ostream& operator << (ostream &s, const EST_Item &a)
611 {
612  a.features().save(s);
613  return s;
614 }
615 
616 
617 void evaluate(EST_Item *a,EST_Features &f)
618 {
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)