Edinburgh Speech Tools 2.4-release
EST_UList.h
1 /************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1996,1997 */
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 /* */
34 /* Author: Richard Caley (rjc@cstr.ed.ac.uk) */
35 /* Date: Mon Jul 21 1997 */
36 /* -------------------------------------------------------------------- */
37 /* Untyped list used as the basis of the TList class */
38 /* */
39 /*************************************************************************/
40
41#ifndef __EST_ULIST_H__
42#define __EST_ULIST_H__
43
44#include <iostream>
45
46using namespace std;
47
48#include "EST_common.h"
49#include "EST_String.h"
50
51class EST_UItem {
52public:
53 void init() { n = NULL; p = NULL;}
54 EST_UItem *n;
55 EST_UItem *p;
56 EST_UItem *next() { return n; }
57 EST_UItem *prev() { return p; }
58};
59
60class EST_UList {
61protected:
62 EST_UItem *h;
63 EST_UItem *t;
64
65protected:
66 void init() { h = NULL; t = NULL; };
67 void clear_and_free(void (*item_free)(EST_UItem *item));
68
69public:
70 EST_UList() { init(); };
71 ~ EST_UList() { clear_and_free(NULL); }
72
73 EST_UItem *nth_pointer(int n) const;
74
75 EST_UItem *insert_after(EST_UItem *ptr, EST_UItem *new_item); // returns pointer to inserted item
76 EST_UItem *insert_before(EST_UItem *ptr, EST_UItem *new_item); // returns pointer to item after inserted item
77
78 // remove single item, return pointer to previous
79 EST_UItem *remove(EST_UItem *ptr, void (*item_free)(EST_UItem *item));
80 EST_UItem *remove(int n, void (*item_free)(EST_UItem *item));
81
82 void exchange(EST_UItem *a, EST_UItem *b);
83 void exchange(int i, int j);
84
85 void reverse(); // in place
86
87 int length() const; // number of items in list
88 int index(EST_UItem *item) const; // position from start of list (head = 0)
89
90 int empty() const // returns true if no items in list
91 {return (h == NULL) ? 1 : 0;};
92 void clear(void)
93 { clear_and_free(NULL); };
94 void append(EST_UItem *item); // add item onto end of list
95
96 void prepend(EST_UItem *item); // add item onto start of list
97
98 EST_UItem *head() const // return pointer to head of list
99 { return h; };
100 EST_UItem *tail() const // return pointer to tail of list
101 { return t; };
102
103
104 static bool operator_eq(const EST_UList &a,
105 const EST_UList &b,
106 bool (*eq)(const EST_UItem *item1, const EST_UItem *item2));
107
108 static int index(const EST_UList &l,
109 const EST_UItem &b,
110 bool (*eq)(const EST_UItem *item1, const EST_UItem *item2));
111
112 static void sort(EST_UList &a,
113 bool (*gt)(const EST_UItem *item1, const EST_UItem *item2));
114 static void qsort(EST_UList &a,
115 bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
116 void (*exchange)(EST_UItem *item1, EST_UItem *item2));
117 static void sort_unique(EST_UList &l,
118 bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
119 bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
120 void (*item_free)(EST_UItem *item));
121 static void merge_sort_unique(EST_UList &l, EST_UList &m,
122 bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
123 bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
124 void (*item_free)(EST_UItem *item));
125};
126
127
128// inline functions in header file
129// everything else in EST_UList.C
130
131
132/* Please don't use these - use the member functions instead!
133inline EST_UItem *next(EST_UItem *ptr)
134{
135 if (ptr != 0)
136 return ptr->n;
137 return 0;
138}
139
140inline EST_UItem *prev(EST_UItem *ptr)
141{
142 if (ptr != 0)
143 return ptr->p;
144 return 0;
145}
146*/
147
148
149#endif