Edinburgh Speech Tools 2.4-release
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
40void 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
55int 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
65int 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
77EST_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
90EST_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
114EST_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
122EST_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
145EST_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
168void 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
212void 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
237void 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
252void 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
266void 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
279bool 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
300int 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
315void 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
345static 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
380static 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
392void 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
400void 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
430void 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}