323 lines
10 KiB
C++
323 lines
10 KiB
C++
/*************************************************************************/
|
|
/* */
|
|
/* 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>
|
|
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
|