150 lines
5.9 KiB
C++
150 lines
5.9 KiB
C++
/************************************************************************/
|
|
/* */
|
|
/* Centre for Speech Technology Research */
|
|
/* University of Edinburgh, UK */
|
|
/* Copyright (c) 1996,1997 */
|
|
/* 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: Richard Caley (rjc@cstr.ed.ac.uk) */
|
|
/* Date: Mon Jul 21 1997 */
|
|
/* -------------------------------------------------------------------- */
|
|
/* Untyped list used as the basis of the TList class */
|
|
/* */
|
|
/*************************************************************************/
|
|
|
|
#ifndef __EST_ULIST_H__
|
|
#define __EST_ULIST_H__
|
|
|
|
#include <iostream>
|
|
|
|
using namespace std;
|
|
|
|
#include "EST_common.h"
|
|
#include "EST_String.h"
|
|
|
|
class EST_UItem {
|
|
public:
|
|
void init() { n = NULL; p = NULL;}
|
|
EST_UItem *n;
|
|
EST_UItem *p;
|
|
EST_UItem *next() { return n; }
|
|
EST_UItem *prev() { return p; }
|
|
};
|
|
|
|
class EST_UList {
|
|
protected:
|
|
EST_UItem *h;
|
|
EST_UItem *t;
|
|
|
|
protected:
|
|
void init() { h = NULL; t = NULL; };
|
|
void clear_and_free(void (*item_free)(EST_UItem *item));
|
|
|
|
public:
|
|
EST_UList() { init(); };
|
|
~ EST_UList() { clear_and_free(NULL); }
|
|
|
|
EST_UItem *nth_pointer(int n) const;
|
|
|
|
EST_UItem *insert_after(EST_UItem *ptr, EST_UItem *new_item); // returns pointer to inserted item
|
|
EST_UItem *insert_before(EST_UItem *ptr, EST_UItem *new_item); // returns pointer to item after inserted item
|
|
|
|
// remove single item, return pointer to previous
|
|
EST_UItem *remove(EST_UItem *ptr, void (*item_free)(EST_UItem *item));
|
|
EST_UItem *remove(int n, void (*item_free)(EST_UItem *item));
|
|
|
|
void exchange(EST_UItem *a, EST_UItem *b);
|
|
void exchange(int i, int j);
|
|
|
|
void reverse(); // in place
|
|
|
|
int length() const; // number of items in list
|
|
int index(EST_UItem *item) const; // position from start of list (head = 0)
|
|
|
|
int empty() const // returns true if no items in list
|
|
{return (h == NULL) ? 1 : 0;};
|
|
void clear(void)
|
|
{ clear_and_free(NULL); };
|
|
void append(EST_UItem *item); // add item onto end of list
|
|
|
|
void prepend(EST_UItem *item); // add item onto start of list
|
|
|
|
EST_UItem *head() const // return pointer to head of list
|
|
{ return h; };
|
|
EST_UItem *tail() const // return pointer to tail of list
|
|
{ return t; };
|
|
|
|
|
|
static bool operator_eq(const EST_UList &a,
|
|
const EST_UList &b,
|
|
bool (*eq)(const EST_UItem *item1, const EST_UItem *item2));
|
|
|
|
static int index(const EST_UList &l,
|
|
const EST_UItem &b,
|
|
bool (*eq)(const EST_UItem *item1, const EST_UItem *item2));
|
|
|
|
static void sort(EST_UList &a,
|
|
bool (*gt)(const EST_UItem *item1, const EST_UItem *item2));
|
|
static void qsort(EST_UList &a,
|
|
bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
|
|
void (*exchange)(EST_UItem *item1, EST_UItem *item2));
|
|
static void sort_unique(EST_UList &l,
|
|
bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
|
|
bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
|
|
void (*item_free)(EST_UItem *item));
|
|
static void merge_sort_unique(EST_UList &l, EST_UList &m,
|
|
bool (*eq)(const EST_UItem *item1, const EST_UItem *item2),
|
|
bool (*gt)(const EST_UItem *item1, const EST_UItem *item2),
|
|
void (*item_free)(EST_UItem *item));
|
|
};
|
|
|
|
|
|
// inline functions in header file
|
|
// everything else in EST_UList.C
|
|
|
|
|
|
/* Please don't use these - use the member functions instead!
|
|
inline EST_UItem *next(EST_UItem *ptr)
|
|
{
|
|
if (ptr != 0)
|
|
return ptr->n;
|
|
return 0;
|
|
}
|
|
|
|
inline EST_UItem *prev(EST_UItem *ptr)
|
|
{
|
|
if (ptr != 0)
|
|
return ptr->p;
|
|
return 0;
|
|
}
|
|
*/
|
|
|
|
|
|
#endif
|