home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / word2x0a.zip / source / fifo.h.dist < prev    next >
Text File  |  1997-03-25  |  3KB  |  165 lines

  1. /* $Id: fifo.h,v 1.4 1997/03/25 23:23:19 dps Exp $ */
  2. /* Generalised fifo */
  3.  
  4. #ifndef __FIFO_H__
  5. #define __FIFO_H__
  6.  
  7. template<class T>
  8. class fifo
  9. {
  10. private:
  11.     typedef struct queue
  12.     {
  13.     const T *data;
  14.     struct queue *next;
  15.     } queue;
  16.     struct queue *start;
  17.     struct queue **end;
  18.     int length;
  19.  
  20. public:
  21.     inline fifo(void)
  22.     {
  23.     start=NULL;
  24.     end=&start;
  25.     length=0;
  26.     }
  27.     inline is_empty(void)
  28.     {
  29.     return (length==0) ? 1 : 0;
  30.     }
  31.     ~fifo(void);
  32.     void enqueue(const T *d);    /* Add to end of queue */
  33.     void insert(const T *d);    /* Add to start of queue */
  34.     void ins_trans(fifo *f);    /* Insert fifo */
  35.     void rev(void);        /* Reverse */
  36.     void transfer(fifo *f);
  37.     const T *dequeue(void);
  38.     friend ostream &operator <<(ostream &, const fifo *);
  39. };
  40.  
  41. template<class T>
  42. fifo<T>::~fifo(void)
  43. {
  44.     struct queue *ptr, *next;
  45.     
  46.     ptr=start;
  47.     while (ptr!=NULL)
  48.     {
  49.     next=ptr->next;
  50.     delete(ptr->data);
  51.     delete(ptr);
  52.     ptr=next;
  53.     }
  54. }
  55.  
  56. template<class T>
  57. void fifo<T>::enqueue(const T *d)
  58. {
  59.     struct queue *q;
  60.     
  61.     q=new(struct queue);
  62.     q->next=NULL;
  63.     q->data=d;
  64.     *end=q;
  65.     end=&(q->next);
  66.     length++;
  67. }
  68.  
  69. template<class T>
  70. void fifo<T>::insert(const T *d)
  71. {
  72.     struct queue *q;
  73.     
  74.     q=new(struct queue);
  75.     q->next=start;
  76.     q->data=d;
  77.     start=q;
  78.     if (q->next==NULL)
  79.     end=&(q->next);
  80.     length++;
  81. }
  82.  
  83. template<class T>
  84. const T *fifo<T>::dequeue(void)
  85. {
  86.     const T *d;
  87.     struct queue *q;
  88.  
  89.     if (length==0)
  90.     return NULL;
  91.  
  92.     q=start;
  93.     d=q->data;
  94.     start=start->next;
  95.     if (--length==0)
  96.     end=&start;
  97.     delete(q);
  98.     return d;
  99. }
  100.  
  101. template <class T>
  102. void fifo<T>::transfer(fifo<T> *d)
  103. {
  104.     *end=d->start;
  105.     end=d->end;
  106.     length+=d->length;
  107.     d->start=NULL;
  108.     d->end=&(d->start);
  109.     d->length=0;
  110. }
  111.  
  112. template<class T>
  113. void fifo<T>::ins_trans(fifo<T> *d)
  114. {
  115.     if (d->length==0)
  116.     return;
  117.  
  118.     *(d->end)=start;
  119.     start=d->start;
  120.     if (*(d->end)==NULL)
  121.     end=d->end;
  122.     length+=d->length;
  123.  
  124.     d->length=0;
  125.     d->start=NULL;
  126.     d->end=&(d->start);
  127. }
  128.  
  129. template<class T>
  130. void fifo<T>::rev(void)
  131. {
  132.     struct queue *p, *n, *hdr, **ep;
  133.  
  134.     if (length==0)
  135.     return;
  136.  
  137.     ep=&(start->next);
  138.     for (hdr=NULL, p=start; p!=NULL; )
  139.     {
  140.     n=p->next;
  141.     p->next=hdr;
  142.     hdr=p;
  143.     p=n;
  144.     }
  145.     start=hdr;
  146.     end=ep;
  147. }
  148.  
  149.  
  150. template<class T>
  151. ostream &operator<<(ostream &os, const fifo<T> *d)
  152. {
  153.     const struct fifo<T>::queue *q;
  154.     
  155.     q=d->start;
  156.     while (q!=NULL)
  157.     {
  158.     os<<(q->data)<<',';
  159.     q=q->next;
  160.     }
  161.     return os;
  162. }
  163.  
  164. #endif /* __FIFO_H__ */
  165.