/* $Id: fifo.h,v 1.4 1997/03/25 23:23:19 dps Exp $ */
/* Generalised fifo */

#ifndef __FIFO_H__
#define __FIFO_H__

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 is_empty(void)
    {
	return (length==0) ? 1 : 0;
    }
    ~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 transfer(fifo *f);
    const T *dequeue(void);
    friend ostream &operator <<(ostream &, const fifo *);
};

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;
    
    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;
    
    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;

    if (length==0)
	return NULL;

    q=start;
    d=q->data;
    start=start->next;
    if (--length==0)
	end=&start;
    delete(q);
    return d;
}

template <class T>
void fifo<T>::transfer(fifo<T> *d)
{
    *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)
{
    if (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;
 
    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 &operator<<(ostream &os, const fifo<T> *d)
{
    const struct fifo<T>::queue *q;
    
    q=d->start;
    while (q!=NULL)
    {
	os<<(q->data)<<',';
	q=q->next;
    }
    return os;
}

#endif /* __FIFO_H__ */