Edinburgh Speech Tools  2.4-release
 All Classes Functions Variables Typedefs Enumerations Enumerator Friends Pages
EST_TList.h
1  /*************************************************************************/
2  /* */
3  /* Centre for Speech Technology Research */
4  /* University of Edinburgh, UK */
5  /* Copyright (c) 1995,1996 */
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 : Paul Taylor */
33  /* Date : April 1995 */
34  /* --------------------------------------------------------------------- */
35  /* Double linked list class */
36  /* */
37  /* Modified by RJC, 21/7/97. Now much of the working code is in the */
38  /* UList class, this template class provides a type safe front end to */
39  /* the untyped list. */
40  /* */
41  /*************************************************************************/
42 
43 #ifndef __Tlist_H__
44 #define __Tlist_H__
45 
46 #include <iostream>
47 
48 using namespace std;
49 
50 #include "EST_common.h"
51 #include "EST_UList.h"
52 #include "EST_TSortable.h"
53 #include "EST_TIterator.h"
54 
55 #include "instantiate/EST_TListI.h"
56 
57 class EST_String;
58 
59 template<class T> class EST_TList;
60 
61 template<class T> class EST_TItem : public EST_UItem {
62 private:
63  static void *operator new(size_t not_used, void *place)
64  {(void)not_used; return place;}
65  static void *operator new(size_t size)
66  {void *p;
67  p = (void *)walloc(char,size);
68  return p;}
69  static void operator delete(void *p)
70  { wfree(p);}
71 
72  static EST_TItem *s_free;
73  static unsigned int s_nfree;
74  static unsigned int s_maxFree;
75 
76 protected:
77  static EST_TItem *make(const T &val);
78  static void release(EST_TItem<T> *it);
79 
80  friend class EST_TList<T>;
81 
82 public:
83  T val;
84 
85  EST_TItem(const T &v) : val(v)
86  { init(); };
87  EST_TItem()
88  { init();};
89 };
90 
91 // pretty name
92 
93 typedef EST_UItem EST_Litem;
94 
95 /**
96 
97 A Template doubly linked list class. This class contains doubly linked
98 lists of a type denoted by {\tt T}. A pointer of type \Ref{EST_Litem}
99 is used to access items in the list. The class supports a variety of
100 ways of adding, removing and accessing items in the list. For examples
101 of how to operate lists, see \Ref{list_example}.
102 
103 Iteration through the list is performed using a pointer of type
104 \Ref{EST_Litem}. See \Ref{Iteration} for example code.
105 
106 */
107 
108 template <class T> class EST_TList : public EST_UList
109 {
110  private:
111  void copy_items(const EST_TList<T> &l);
112  public:
113  void init() { EST_UList::init(); };
114  static void free_item(EST_UItem *item);
115 
116  /**@name Constructor functions */
117  //@{
118  /// default constructor
119  EST_TList() { };
120  /// copy constructor
121  EST_TList(const EST_TList<T> &l);
122  ~ EST_TList() { clear_and_free(free_item); }
123  //@}
124 
125  /**@name Access functions for reading and writing items.
126  See \Ref{EST_TList_Accessing} for examples.*/
127 
128  //@{
129 
130  /** return the value associated with the EST_Litem pointer. This
131  has the same functionality as the overloaded () operator.
132  */
133  T &item(const EST_Litem *p)
134  { return ((EST_TItem<T> *)p) -> val; };
135  /** return a const value associated with the EST_Litem pointer.*/
136  const T &item(const EST_Litem *p) const
137  { return ((EST_TItem<T> *)p) -> val; };
138  /// return the Nth value
139  T &nth(int n)
140  { return item(nth_pointer(n)); };
141  /// return a const Nth value
142  const T &nth(int n) const
143  { return item(nth_pointer(n)); };
144 
145  /// return const reference to first item in list
146  const T &first() const
147  { return item(head()); };
148  /// return const reference to last item in list
149  const T &last() const
150  { return item(tail()); };
151  /** return reference to first item in list
152  * @see last
153  */
154  T &first()
155  { return item(head()); };
156  /// return reference to last item in list
157  T &last()
158  { return item(tail()); };
159 
160  /// return const reference to item in list pointed to by {\tt ptr}
161  const T &operator () (const EST_Litem *ptr) const
162  { return item(ptr); };
163  /// return non-const reference to item in list pointed to by {\tt ptr}
164  T &operator () (const EST_Litem *ptr)
165  { return item(ptr); };
166 
167  //@}
168 
169  /**@name Removing items in a list.
170  more.
171  */
172  //@{
173  /** remove item pointed to by {\tt ptr}, return pointer to previous item.
174  See \Ref{Removing} for example code.*/
175  EST_Litem *remove(EST_Litem *ptr)
176  { return EST_UList::remove(ptr, free_item); };
177 
178  /// remove nth item, return pointer to previous item
179  EST_Litem *remove_nth(int n)
180  { return EST_UList::remove(n, free_item); };
181 
182  //@}
183 
184 
185  /**@name Adding items to a list.
186  In all cases, a complete copy of
187  the item is made and added to the list. See \Ref{Addition} for examples.
188  */
189  //@{
190  /// add item onto end of list
191  void append(const T &item)
192  { EST_UList::append(EST_TItem<T>::make(item)); };
193  /// add item onto start of list
194  void prepend(const T &item)
195  { EST_UList::prepend(EST_TItem<T>::make(item)); };
196 
197  /** add {\tt item} after position given by {\tt ptr}, return pointer
198  to added item. */
199 
200  EST_Litem *insert_after(EST_Litem *ptr, const T &item)
201  { return EST_UList::insert_after(ptr, EST_TItem<T>::make(item)); };
202 
203  /** add {\tt item} before position given by {\tt ptr}, return
204  pointer to added item. */
205 
206  EST_Litem *insert_before(EST_Litem *ptr, const T &item)
207  { return EST_UList::insert_before(ptr, EST_TItem<T>::make(item)); };
208 
209  //@}
210 
211  /**@name Exchange */
212  //@{
213  /// exchange 1
214  void exchange(EST_Litem *a, EST_Litem *b)
215  { EST_UList::exchange(a, b); };
216  /// exchange 2
217  void exchange(int i, int j)
218  { EST_UList::exchange(i,j); };
219  /// exchange 3
220  static void exchange_contents(EST_Litem *a, EST_Litem *b);
221  //@}
222 
223  /**@name General functions */
224  //@{
225  /// make full copy of list
226  EST_TList<T> &operator=(const EST_TList<T> &a);
227  /// Add list onto end of existing list
228  EST_TList<T> &operator +=(const EST_TList<T> &a);
229 
230  /// print list
231  friend ostream& operator << (ostream &st, EST_TList<T> const &list) {
232  EST_Litem *ptr;
233  for (ptr = list.head(); ptr != 0; ptr = ptr->next())
234  st << list.item(ptr) << " ";
235  return st;
236  }
237 
238  /// remove all items in list
239  void clear(void)
240  { clear_and_free(free_item); };
241  //@}
242 
243  // Iteration support
244 
245 protected:
246  struct IPointer { EST_Litem *p; };
247 
248  void point_to_first(IPointer &ip) const { ip.p = head(); }
249  void move_pointer_forwards(IPointer &ip) const { ip.p = ip.p->next(); }
250  bool points_to_something(const IPointer &ip) const { return ip.p != NULL; }
251  T &points_at(const IPointer &ip) { return item(ip.p); }
252 
253  friend class EST_TIterator< EST_TList<T>, IPointer, T >;
254  friend class EST_TRwIterator< EST_TList<T>, IPointer, T >;
255 
256 public:
257  typedef T Entry;
258  typedef EST_TIterator< EST_TList<T>, IPointer, T > Entries;
259  typedef EST_TRwIterator< EST_TList<T>, IPointer, T > RwEntries;
260 
261 };
262 
263 
264 template<class T>
265 bool operator==(const EST_TList<T> &a, const EST_TList<T> &b)
266 {
267  return EST_UList::operator_eq(a, b, EST_TSortable<T>::items_eq);
268 }
269 
270 template<class T>
271 int index(EST_TList<T> &l, T& val, bool (*eq)(const EST_UItem *, const EST_UItem *) = NULL)
272 {
273  EST_TItem<T> item(val);
274  return EST_UList::index(l, item, eq?eq:EST_TSortable<T>::items_eq);
275 }
276 
277 template<class T>
278 void sort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
279 {
280  EST_UList::sort(a, gt?gt:EST_TSortable<T>::items_gt);
281 }
282 
283 template<class T>
284 void ptr_sort(EST_TList<T> &a)
285 {
286  EST_UList::sort(a, EST_TSortable<T *>::items_gt);
287 }
288 
289 template<class T>
290 void qsort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
291 {
292  EST_UList::qsort(a, gt?gt:EST_TSortable<T>::items_gt, EST_TList<T>::exchange_contents);
293 }
294 
295 template<class T>
296 void ptr_qsort(EST_TList<T> &a)
297 {
299 }
300 
301 template<class T>
302 void sort_unique(EST_TList<T> &l)
303 {
304  EST_UList::sort_unique(l,
308 }
309 
310 template<class T>
311 void merge_sort_unique(EST_TList<T> &l, EST_TList<T> &m)
312 {
313  EST_UList::merge_sort_unique(l, m,
317 }
318 
319 template<class T>
320 const char *error_name(EST_TList<T> val) { (void)val; return "<<TLIST>>"; }
321 
322 #endif