Loading...
Searching...
No Matches
EST_TList.h
/*************************************************************************/
/* */
/* Centre for Speech Technology Research */
/* University of Edinburgh, UK */
/* Copyright (c) 1995,1996 */
/* All Rights Reserved. */
/* Permission is hereby granted, free of charge, to use and distribute */
/* this software and its documentation without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of this work, and to */
/* permit persons to whom this work is furnished to do so, subject to */
/* the following conditions: */
/* 1. The code must retain the above copyright notice, this list of */
/* conditions and the following disclaimer. */
/* 2. Any modifications must be clearly marked as such. */
/* 3. Original authors' names are not deleted. */
/* 4. The authors' names are not used to endorse or promote products */
/* derived from this software without specific prior written */
/* permission. */
/* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
/* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
/* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
/* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
/* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
/* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
/* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
/* THIS SOFTWARE. */
/* */
/*************************************************************************/
/* */
/* Author : Paul Taylor */
/* Date : April 1995 */
/* --------------------------------------------------------------------- */
/* Double linked list class */
/* */
/* Modified by RJC, 21/7/97. Now much of the working code is in the */
/* UList class, this template class provides a type safe front end to */
/* the untyped list. */
/* */
/*************************************************************************/
#ifndef __Tlist_H__
#define __Tlist_H__
#include <iostream>
using namespace std;
#include "EST_common.h"
#include "EST_UList.h"
#include "EST_TSortable.h"
#include "EST_TIterator.h"
#include "instantiate/EST_TListI.h"
class EST_String;
template<class T> class EST_TList;
template<class T> class EST_TItem : public EST_UItem {
private:
static void *operator new(size_t not_used, void *place)
{(void)not_used; return place;}
static void *operator new(size_t size)
{void *p;
p = (void *)walloc(char,size);
return p;}
static void operator delete(void *p)
{ wfree(p);}
static EST_TItem *s_free;
static unsigned int s_nfree;
static unsigned int s_maxFree;
protected:
static EST_TItem *make(const T &val);
static void release(EST_TItem<T> *it);
friend class EST_TList<T>;
public:
T val;
EST_TItem(const T &v) : val(v)
{ init(); };
EST_TItem()
{ init();};
};
// pretty name
typedef EST_UItem EST_Litem;
/**
A Template doubly linked list class. This class contains doubly linked
lists of a type denoted by {\tt T}. A pointer of type \Ref{EST_Litem}
is used to access items in the list. The class supports a variety of
ways of adding, removing and accessing items in the list. For examples
of how to operate lists, see \Ref{list_example}.
Iteration through the list is performed using a pointer of type
\Ref{EST_Litem}. See \Ref{Iteration} for example code.
*/
template <class T> class EST_TList : public EST_UList
{
private:
void copy_items(const EST_TList<T> &l);
public:
void init() { EST_UList::init(); };
static void free_item(EST_UItem *item);
/**@name Constructor functions */
//@{
/// default constructor
EST_TList() { };
/// copy constructor
EST_TList(const EST_TList<T> &l);
~ EST_TList() { clear_and_free(free_item); }
//@}
/**@name Access functions for reading and writing items.
See \Ref{EST_TList_Accessing} for examples.*/
//@{
/** return the value associated with the EST_Litem pointer. This
has the same functionality as the overloaded () operator.
*/
T &item(const EST_Litem *p)
{ return ((EST_TItem<T> *)p) -> val; };
/** return a const value associated with the EST_Litem pointer.*/
const T &item(const EST_Litem *p) const
{ return ((EST_TItem<T> *)p) -> val; };
/// return the Nth value
T &nth(int n)
{ return item(nth_pointer(n)); };
/// return a const Nth value
const T &nth(int n) const
{ return item(nth_pointer(n)); };
/// return const reference to first item in list
const T &first() const
{ return item(head()); };
/// return const reference to last item in list
const T &last() const
{ return item(tail()); };
/** return reference to first item in list
* @see last
*/
T &first()
{ return item(head()); };
/// return reference to last item in list
T &last()
{ return item(tail()); };
/// return const reference to item in list pointed to by {\tt ptr}
const T &operator () (const EST_Litem *ptr) const
{ return item(ptr); };
/// return non-const reference to item in list pointed to by {\tt ptr}
T &operator () (const EST_Litem *ptr)
{ return item(ptr); };
//@}
/**@name Removing items in a list.
more.
*/
//@{
/** remove item pointed to by {\tt ptr}, return pointer to previous item.
See \Ref{Removing} for example code.*/
EST_Litem *remove(EST_Litem *ptr)
{ return EST_UList::remove(ptr, free_item); };
/// remove nth item, return pointer to previous item
EST_Litem *remove_nth(int n)
{ return EST_UList::remove(n, free_item); };
//@}
/**@name Adding items to a list.
In all cases, a complete copy of
the item is made and added to the list. See \Ref{Addition} for examples.
*/
//@{
/// add item onto end of list
void append(const T &item)
{ EST_UList::append(EST_TItem<T>::make(item)); };
/// add item onto start of list
void prepend(const T &item)
{ EST_UList::prepend(EST_TItem<T>::make(item)); };
/** add {\tt item} after position given by {\tt ptr}, return pointer
to added item. */
EST_Litem *insert_after(EST_Litem *ptr, const T &item)
{ return EST_UList::insert_after(ptr, EST_TItem<T>::make(item)); };
/** add {\tt item} before position given by {\tt ptr}, return
pointer to added item. */
EST_Litem *insert_before(EST_Litem *ptr, const T &item)
{ return EST_UList::insert_before(ptr, EST_TItem<T>::make(item)); };
//@}
/**@name Exchange */
//@{
/// exchange 1
void exchange(EST_Litem *a, EST_Litem *b)
{ EST_UList::exchange(a, b); };
/// exchange 2
void exchange(int i, int j)
{ EST_UList::exchange(i,j); };
/// exchange 3
static void exchange_contents(EST_Litem *a, EST_Litem *b);
//@}
/**@name General functions */
//@{
/// make full copy of list
EST_TList<T> &operator=(const EST_TList<T> &a);
/// Add list onto end of existing list
EST_TList<T> &operator +=(const EST_TList<T> &a);
/// print list
friend ostream& operator << (ostream &st, EST_TList<T> const &list) {
EST_Litem *ptr;
for (ptr = list.head(); ptr != 0; ptr = ptr->next())
st << list.item(ptr) << " ";
return st;
}
/// remove all items in list
void clear(void)
{ clear_and_free(free_item); };
//@}
// Iteration support
protected:
struct IPointer { EST_Litem *p; };
void point_to_first(IPointer &ip) const { ip.p = head(); }
void move_pointer_forwards(IPointer &ip) const { ip.p = ip.p->next(); }
bool points_to_something(const IPointer &ip) const { return ip.p != NULL; }
T &points_at(const IPointer &ip) { return item(ip.p); }
friend class EST_TIterator< EST_TList<T>, IPointer, T >;
friend class EST_TRwIterator< EST_TList<T>, IPointer, T >;
public:
typedef T Entry;
typedef EST_TIterator< EST_TList<T>, IPointer, T > Entries;
typedef EST_TRwIterator< EST_TList<T>, IPointer, T > RwEntries;
};
template<class T>
bool operator==(const EST_TList<T> &a, const EST_TList<T> &b)
{
return EST_UList::operator_eq(a, b, EST_TSortable<T>::items_eq);
}
template<class T>
bool operator!=(const EST_TList<T> &a, const EST_TList<T> &b)
{
return !(a==b);
}
template<class T>
int index(EST_TList<T> &l, T& val, bool (*eq)(const EST_UItem *, const EST_UItem *) = NULL)
{
EST_TItem<T> item(val);
return EST_UList::index(l, item, eq?eq:EST_TSortable<T>::items_eq);
}
template<class T>
void sort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
{
EST_UList::sort(a, gt?gt:EST_TSortable<T>::items_gt);
}
template<class T>
void ptr_sort(EST_TList<T> &a)
{
EST_UList::sort(a, EST_TSortable<T *>::items_gt);
}
template<class T>
void qsort(EST_TList<T> &a, bool (*gt)(const EST_UItem *, const EST_UItem *) = NULL)
{
EST_UList::qsort(a, gt?gt:EST_TSortable<T>::items_gt, EST_TList<T>::exchange_contents);
}
template<class T>
void ptr_qsort(EST_TList<T> &a)
{
EST_UList::qsort(a, EST_TSortable<T *>::items_gt, EST_TList<T>::exchange_contents);
}
template<class T>
void sort_unique(EST_TList<T> &l)
{
EST_UList::sort_unique(l,
EST_TSortable<T>::items_eq,
EST_TSortable<T>::items_gt,
EST_TList<T>::free_item);
}
template<class T>
void merge_sort_unique(EST_TList<T> &l, EST_TList<T> &m)
{
EST_UList::merge_sort_unique(l, m,
EST_TSortable<T>::items_eq,
EST_TSortable<T>::items_gt,
EST_TList<T>::free_item);
}
template<class T>
const char *error_name(EST_TList<T> val) { (void)val; return "<<TLIST>>"; }
#endif
EST_String
Definition EST_String.h:70
IPointer
EST_TItem
Definition EST_TList.h:61
EST_TList
Definition EST_TList.h:109
EST_TList::exchange
void exchange(EST_Litem *a, EST_Litem *b)
exchange 1
Definition EST_TList.h:214
EST_TList::remove_nth
EST_Litem * remove_nth(int n)
remove nth item, return pointer to previous item
Definition EST_TList.h:179
EST_TList::last
const T & last() const
return const reference to last item in list
Definition EST_TList.h:149
EST_TList::item
T & item(const EST_Litem *p)
Definition EST_TList.h:133
EST_TList::first
T & first()
Definition EST_TList.h:154
EST_TList::operator<<
friend ostream & operator<<(ostream &st, EST_TList< T > const &list)
print list
Definition EST_TList.h:231
EST_TList::nth
T & nth(int n)
return the Nth value
Definition EST_TList.h:139
EST_TList::operator=
EST_TList< T > & operator=(const EST_TList< T > &a)
make full copy of list
Definition EST_TList.cc:113
EST_TList::clear
void clear(void)
remove all items in list
Definition EST_TList.h:239
EST_TList::append
void append(const T &item)
add item onto end of list
Definition EST_TList.h:191
EST_TList::last
T & last()
return reference to last item in list
Definition EST_TList.h:157
EST_TList::EST_TList
EST_TList()
default constructor
Definition EST_TList.h:119
EST_TList::remove
EST_Litem * remove(EST_Litem *ptr)
Definition EST_TList.h:175
EST_TList::exchange_contents
static void exchange_contents(EST_Litem *a, EST_Litem *b)
exchange 3
Definition EST_TList.cc:98
EST_TList::EST_TList
EST_TList(const EST_TList< T > &l)
copy constructor
Definition EST_TList.cc:92
EST_TList::operator+=
EST_TList< T > & operator+=(const EST_TList< T > &a)
Add list onto end of existing list.
Definition EST_TList.cc:121
EST_TList::insert_after
EST_Litem * insert_after(EST_Litem *ptr, const T &item)
Definition EST_TList.h:200
EST_TList::insert_before
EST_Litem * insert_before(EST_Litem *ptr, const T &item)
Definition EST_TList.h:206
EST_TList::exchange
void exchange(int i, int j)
exchange 2
Definition EST_TList.h:217
EST_TList::item
const T & item(const EST_Litem *p) const
Definition EST_TList.h:136
EST_TList::operator()
const T & operator()(const EST_Litem *ptr) const
return const reference to item in list pointed to by {\tt ptr}
Definition EST_TList.h:161
EST_TList::first
const T & first() const
return const reference to first item in list
Definition EST_TList.h:146
EST_TList::prepend
void prepend(const T &item)
add item onto start of list
Definition EST_TList.h:194
EST_TList::nth
const T & nth(int n) const
return a const Nth value
Definition EST_TList.h:142
EST_UItem
Definition EST_UList.h:51
EST_TList::IPointer
Definition EST_TList.h:246