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