Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_UList.cc
1 /*************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1997,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 /* */
32 /* Author: Richard Caley (rjc@cstr.ed.ac.uk) */
33 /* Date: Mon Jul 21 1997 */
34 /* -------------------------------------------------------------------- */
35 /* Untyped list used as the basis of the TList class */
36 /* */
37 /*************************************************************************/
38 #include <EST_UList.h>
39 
40 void EST_UList::clear_and_free(void (*item_free)(EST_UItem *p))
41 {
42  EST_UItem *q, *np;
43 
44  for (q=head(); q != 0; q = np)
45  {
46  np=q->next();
47  if (item_free)
48  item_free(q);
49  else
50  delete q;
51  }
52  h = t = 0;
53 }
54 
55 int EST_UList::length() const
56 {
57  EST_UItem *ptr;
58  int n = 0;
59 
60  for (ptr = head(); ptr != 0; ptr = ptr->next())
61  ++n;
62  return n;
63 }
64 
65 int EST_UList::index(EST_UItem *item) const
66 {
67  EST_UItem *ptr;
68  int n = 0;
69 
70  for (ptr = head(); ptr != 0; ptr = ptr->next(), ++n)
71  if (item == ptr)
72  return n;
73 
74  return -1;
75 }
76 
77 EST_UItem *EST_UList::nth_pointer(int n) const
78 {
79  EST_UItem *ptr;
80  int i;
81 
82  for (i = 0, ptr = head(); ptr != 0; ptr = ptr->next(), ++i)
83  if (i == n)
84  return ptr;
85 
86  cerr << "Requested item #" << n << " off end of list" << endl;
87  return head();
88 }
89 
90 EST_UItem * EST_UList::remove(EST_UItem *item,
91  void (*free_item)(EST_UItem *item))
92 {
93  if (item == 0)
94  return 0;
95 
96  EST_UItem *prev = item->p;
97  if (item->p == 0) // at start
98  h = item->n;
99  else
100  item->p->n = item->n;
101  if (item->n == 0) // at end
102  t = item->p;
103  else
104  item->n->p = item->p;
105 
106  if (free_item)
107  free_item(item);
108  else
109  delete item;
110 
111  return prev;
112 }
113 
114 EST_UItem * EST_UList::remove(int n,
115  void (*item_free)(EST_UItem *item))
116 {
117  return remove(nth_pointer(n), item_free);
118 }
119 
120 // This should check if the incoming prev_item actually is in the list
121 
122 EST_UItem *EST_UList::insert_after(EST_UItem *prev_item, EST_UItem *new_item)
123 {
124  if (new_item == 0)
125  return new_item;
126  if (prev_item == 0) // insert it at start of list
127  {
128  new_item->n = h;
129  h = new_item;
130  }
131  else
132  {
133  new_item->n = prev_item->n;
134  prev_item->n = new_item;
135  }
136  new_item->p = prev_item;
137  if (new_item->n == 0)
138  t = new_item;
139  else
140  new_item->n->p = new_item;
141 
142  return new_item;
143 }
144 
145 EST_UItem *EST_UList::insert_before(EST_UItem *next_item, EST_UItem *new_item)
146 {
147  if (new_item == 0)
148  return new_item;
149  if (next_item == 0) // put it on the end of the list
150  {
151  new_item->p = t;
152  t = new_item;
153  }
154  else
155  {
156  new_item->p = next_item->p;
157  next_item->p = new_item;
158  }
159  new_item->n = next_item;
160  if (new_item->p == 0)
161  h = new_item;
162  else
163  new_item->p->n = new_item;
164 
165  return next_item;
166 }
167 
168 void EST_UList::exchange(EST_UItem *a, EST_UItem *b)
169 {
170 
171  if (a==b)
172  return;
173 
174  if ((a==0) || (b==0))
175  {
176  cerr << "EST_UList:exchange: can't exchange NULL items" << endl;
177  return;
178  }
179 
180  // I know this isn't very readable but there are eight pointers
181  // that need to be changed, and half of them are trivial back pointers
182  // care need only be taken when b and a are adjacent, this actual
183  // sets p and n twice if they are adjacent but still gets the right answer
184  EST_UItem *ap=a->p,*an=a->n,*bn=b->n,*bp=b->p;
185 
186  a->n = bn == a ? b : bn;
187  if (a->n)
188  a->n->p = a;
189  a->p = bp == a ? b : bp;
190  if (a->p)
191  a->p->n = a;
192 
193  b->n = an == b ? a : an;
194  if (b->n)
195  b->n->p = b;
196  b->p = ap == b ? a : ap;
197  if (b->p)
198  b->p->n = b;
199 
200  // Fix t and h
201  if (a == h)
202  h = b;
203  else if (b == h)
204  h = a;
205  else if (a == t)
206  t = b;
207  else if (b == t)
208  t = a;
209 
210 }
211 
212 void EST_UList::exchange(int i, int j)
213 {
214 
215  EST_UItem *p;
216  EST_UItem *a=0,*b=0;
217  int k;
218 
219  for (k=0,p = head(); p != 0; p = p->next(),k++)
220  {
221  if(i==k)
222  a = p;
223  if(j==k)
224  b = p;
225  }
226 
227  if ((a==0) || (b==0))
228  {
229  cerr << "EST_UList:exchange: can't exchange items " << i <<
230  " and " << j << " (off end of list)" << endl;
231  return;
232  }
233 
234  exchange(a,b);
235 }
236 
237 void EST_UList::reverse()
238 {
239  EST_UItem *p,*q;
240 
241  for (p=head(); p != 0; p=q)
242  {
243  q = p->n;
244  p->n = p->p;
245  p->p = q;
246  }
247  q = h;
248  h = t;
249  t = q;
250 }
251 
252 void EST_UList::append(EST_UItem *new_item)
253 {
254 
255  if (new_item == 0) return;
256 
257  new_item->n = 0;
258  new_item->p = t;
259  if (t == 0)
260  h = new_item;
261  else
262  t->n = new_item;
263  t = new_item;
264 }
265 
266 void EST_UList::prepend(EST_UItem *new_item)
267 {
268  if (new_item == 0) return;
269 
270  new_item->p = 0;
271  new_item->n = h;
272  if (h == 0)
273  t = new_item;
274  else
275  h->p = new_item;
276  h = new_item;
277 }
278 
279 bool EST_UList::operator_eq(const EST_UList &a,
280  const EST_UList &b,
281  bool (*eq)(const EST_UItem *item1, const EST_UItem *item2))
282 {
283  EST_UItem *p,*q;
284  q=b.head();
285  for (p = a.head(); p != NULL; p = p->next()){
286  if(q == NULL)
287  return false;
288  if(eq(q, p))
289  q=q->next();
290  else
291  return false;
292  }
293 
294  if(q == NULL)
295  return true;
296  else
297  return false;
298 }
299 
300 int EST_UList::index(const EST_UList &l,
301  const EST_UItem &val,
302  bool (*eq)(const EST_UItem *item1, const EST_UItem *item2))
303 {
304 
305  EST_UItem *ptr;
306  int n = 0;
307 
308  for (ptr = l.head(); ptr != 0; ptr = ptr->next(), ++n)
309  if (eq(&val,ptr))
310  return n;
311 
312  return -1;
313 }
314 
315 void EST_UList::sort(EST_UList &l,
316  bool (*gt)(const EST_UItem *item1,
317  const EST_UItem *item2))
318 {
319 
320  // just bubble sort for now
321  // use EST_String::operator > for comparisons
322 
323  EST_UItem *l_ptr,*m_ptr;
324  bool sorted=false;
325 
326  while(!sorted){
327  sorted=true;
328 
329  for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
330 
331  m_ptr=l_ptr->next();
332  if(m_ptr != 0)
333  if(gt(l_ptr, m_ptr)){
334  l.exchange(l_ptr,m_ptr);
335  sorted=false;
336  }
337  }
338  }
339 
340 }
341 
342 // quicksort from 'Algorithms'
343 // by Cormen, Leiserson & Rivest
344 
345 static EST_UItem *partition(EST_UItem *p, EST_UItem *r,
346  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
347  void (*exchange)(EST_UItem *item1, EST_UItem *item2))
348 {
349  // this can be tidied up / sped up
350 
351  EST_UItem *i,*j,*i2,*j2;
352  EST_UItem *x = p;
353 
354  i = p;
355  j = r;
356 
357  while(true){
358 
359  while(gt(j, x) )
360  j = j->prev();
361 
362  while(gt(x, i))
363  i = i->next();
364 
365  if((i != j) && (i->prev() != j)){
366  i2=i;
367  j2=j;
368  i=i->next();
369  j=j->prev();
370  exchange(i2,j2);
371 
372  }else
373  return j;
374 
375  }
376  return NULL;
377 }
378 
379 
380 static void qsort_sub(EST_UList &l, EST_UItem *p, EST_UItem *r,
381  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
382  void (*exchange)(EST_UItem *item1, EST_UItem *item2))
383 {
384  EST_UItem *q;
385  if(p != r){
386  q = partition(p,r, gt, exchange);
387  qsort_sub(l,p,q, gt, exchange);
388  qsort_sub(l,q->next(),r, gt, exchange);
389  }
390 }
391 
392 void EST_UList::qsort(EST_UList &l,
393  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
394  void (*exchange)(EST_UItem *item1, EST_UItem *item2))
395 {
396  qsort_sub(l,l.head(),l.tail(), gt, exchange);
397 }
398 
399 
400 void EST_UList::sort_unique(EST_UList &l,
401  bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
402  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
403  void (*item_free)(EST_UItem *item))
404 {
405  // as sort(..) but delete any repeated items
406 
407  EST_UItem *l_ptr,*m_ptr;
408  bool sorted=false;
409 
410  while(!sorted){
411  sorted=true;
412 
413  for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
414 
415  m_ptr=l_ptr->next();
416  if(m_ptr != 0)
417  {
418  if(gt(l_ptr, m_ptr)){
419  l.exchange(l_ptr,m_ptr);
420  sorted=false;
421  } else if(eq(l_ptr, m_ptr)){
422  l.remove(m_ptr, item_free);
423  sorted=false;
424  }
425  }
426  }
427  }
428 }
429 
430 void EST_UList::merge_sort_unique(EST_UList &l, EST_UList &m,
431  bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
432  bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
433  void (*item_free)(EST_UItem *item))
434 {
435  // keep all unique items in l, and add any new items from m to l
436 
437  EST_UItem *l_ptr,*m_ptr;
438  bool flag;
439 
440  // make sure
441  sort_unique(l, eq, gt, item_free);
442 
443  for(m_ptr=m.head(); m_ptr != 0; m_ptr=m_ptr->next()){
444 
445  // try and put item from m in list
446  flag=false;
447  for(l_ptr=l.head(); l_ptr != 0; l_ptr=l_ptr->next()){
448  if( gt(l_ptr, m_ptr) ){
449  l.insert_before(l_ptr, m_ptr);
450  flag=true;
451  break;
452  }else if( eq(m_ptr, l_ptr) ){
453  flag=true;
454  break;
455  }
456  }
457  // or try and append it
458  if(!flag && ( gt(m_ptr, l.tail()) ) )
459  l.append(m_ptr);
460  }
461 }