/* Generalised fifo */

/* $Id: fifo.h,v 1.17 1998/04/19 15:44:31 dps Exp $ */
/* Generalised fifo */

#ifndef __FIFO_H__
#define __FIFO_H__

#include <iostream.h>
#include <stddef.h>
#ifndef NULL
#define NULL (void *) 0
#endif /* NULL */

template<class T>
class fifo
{
private:
typedef struct queue
{
const T *data;
struct queue *next;
} queue;
struct queue *start;
struct queue **end;
int length;

public:
inline fifo(void)
{
start=NULL;
end=&start;
length=0;
}
inline int is_empty(void)
{
#ifdef CONSIST_CHECK
if (end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif
return (length==0) ? 1 : 0;
}
inline int qlen(void)
{
return length;
}
~fifo(void);
void enqueue(const T *d); /* Add to end of queue */
void insert(const T *d); /* Add to start of queue */
void ins_trans(fifo *f); /* Insert fifo */
void rev(void); /* Reverse */
void clear(void); /* Wipe list to empty */
void transfer(fifo *f);
const T *dequeue(void);
ostream &__print_fifo(ostream &) const; /* Print */
};

#ifndef __NO_FIFO_FUNCTIONS__

template<class T>
void fifo<T>::clear(void)
{
struct queue *ptr, *next;

ptr=start;
while (ptr!=NULL)
{
next=ptr->next;
delete(ptr->data);
delete(ptr);
ptr=next;
}
start=NULL;
end=&start;
length=0;
}

template<class T>
fifo<T>::~fifo(void)
{
struct queue *ptr, *next;

ptr=start;
while (ptr!=NULL)
{
next=ptr->next;
delete(ptr->data);
delete(ptr);
ptr=next;
}
}

template<class T>
void fifo<T>::enqueue(const T *d)
{
struct queue *q;

#ifdef DEBUG_FIFO
cerr<<"Queue "<<(void *) d<<"\n";
#endif
q=new(struct queue);
q->next=NULL;
q->data=d;
*end=q;
end=&(q->next);
length++;
}

template<class T>
void fifo<T>::insert(const T *d)
{
struct queue *q;
#ifdef CONSIST_CHECK
if (end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

q=new(struct queue);
q->next=start;
q->data=d;
start=q;
if (q->next==NULL)
end=&(q->next);
length++;
}

template<class T>
const T *fifo<T>::dequeue(void)
{
const T *d;
struct queue *q;
#ifdef CONSIST_CHECK
if (end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

if (length==0)
return NULL;

q=start;
d=q->data;
#ifdef DEBUG_FIFO
cerr<<"Dequeue "<<(void *) d<<"\n";
#endif
start=start->next;
if (--length==0)
end=&start;
delete(q);
return d;
}

template <class T>
void fifo<T>::transfer(fifo<T> *d)
{
#ifdef CONSIST_CHECK
if (end==NULL || d->end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

if (d==NULL || d->length==0)
return;

*end=d->start;
end=d->end;
length+=d->length;
d->start=NULL;
d->end=&(d->start);
d->length=0;
}

template<class T>
void fifo<T>::ins_trans(fifo<T> *d)
{
#ifdef CONSIST_CHECK
if (end==NULL || d->end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

if (d==NULL || d->length==0)
return;

*(d->end)=start;
start=d->start;
if (*(d->end)==NULL)
end=d->end;
length+=d->length;

d->length=0;
d->start=NULL;
d->end=&(d->start);
}

template<class T>
void fifo<T>::rev(void)
{
struct queue *p, *n, *hdr, **ep;
#ifdef CONSIST_CHECK
if (end==NULL || d->end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

if (length==0)
return;

ep=&(start->next);
for (hdr=NULL, p=start; p!=NULL; )
{
n=p->next;
p->next=hdr;
hdr=p;
p=n;
}
start=hdr;
end=ep;
}

template<class T>
ostream &fifo<T>::__print_fifo(ostream &os) const
{
const struct fifo<T>::queue *q;

#ifdef CONSIST_CHECK
if (end==NULL || this->end==NULL)
{
cerr<<"Oops! end of list is NULL\n";
exit(1);
}
#endif

q=this->start;
while (q!=NULL)
{
os<<(q->data)<<',';
q=q->next;
}
return os;
}

template<class T>
inline ostream &operator << (ostream &os, const fifo<T> *d)
{
d->__print_fifo(os);
return os;
}

#endif /* not __NO_FIFO_FUNCTIONS__ */
#endif /* __FIFO_H__ */