/* $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__ */