OS/2 Shareware BBS: 5 Edit/05-Edit.zip/word2x0a.zip/source/fifo.h

C/C++ Source or Header | 1998-04-20 | 4KB | 266 lines

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