linkeddeque.h

来自「用于词法分析的词法分析器」· C头文件 代码 · 共 156 行

/*
  $Id: LinkedDeque.h,v 1.2 1997/02/02 01:31:05 matt Exp $

  Deque as double-linked list.
  
  (c) Mar 1995 Matt Phillips.
  */

#ifndef _LDEQUE_H
#define _LDEQUE_H

#include "Deque.h"
#include "DblLinkList.h"

////////////////// LinkedDequeImp

template <class T, class E> class LinkedDequeImp :
  public Deque<T>, protected DblLinkListImp<T, E>
{
public:

  typedef class LinkedDequeImpIter<T, E> Iterator;

  LinkedDequeImp () : tail (0) {}

  const char *name () const {return Deque<T>::name ();}
  int nItems () const {return DblLinkListImp<T, E>::nItems ();}
  int isFull () const {return DblLinkListImp<T, E>::isFull ();}
  int isEmpty () const {return DblLinkListImp<T, E>::isEmpty ();}

  virtual void addHead (T &i);
  virtual void addTail (T &i);
  virtual void removeHead ();
  virtual void removeTail ();
   
  virtual T &peekHead () const {DEQUE_PEEK (head); return head->ref ();}
  virtual T &peekTail () const {DEQUE_PEEK (tail); return tail->ref ();}
   
  virtual void clear () {DblLinkListImp<T, E>::clear (); tail = 0;}

  virtual Iterator *makeIter () const {return new Iterator (*this);}
   
protected:
   
  E *tail;

  friend class Iterator;
};

template <class T, class E> class LinkedDequeImpIter :
  public DblLinkListImpIter<T, E>
{
public:
   
  LinkedDequeImpIter (const LinkedDequeImp<T, E> &d) :
    DblLinkListImpIter<T, E> (d), tail (d.tail) {}
   
  virtual void resetEnd () {i = tail;}

protected:

  E *tail;
};

template <class T, class E>
void LinkedDequeImp<T, E>::addHead (T &d)
{
  E *i = new E (d);
   
  if (_nItems > 0)
  {
    i->next = head;
    i->prev = 0;
    head->prev = i;
    head = i;
  } else
  {
    head = tail = i;
    i->next = i->prev = 0;
  }
   
  _nItems++;
}

template <class T, class E>
void LinkedDequeImp<T, E>::addTail (T &d)
{
  E *i = new E (d);
   
  if (_nItems > 0)
  {
    i->next = 0;
    i->prev = tail;
    tail->next = i;
    tail = i;
  } else
  {
    head = tail = i;
    i->next = i->prev = 0;
  }
   
  _nItems++;
}

template <class T, class E>
void LinkedDequeImp<T, E>::removeHead ()
{
  if (_nItems > 0)
  {
    if (head == tail)
    {
      delete head;
      head = tail = 0;
    } else
    {
      E *t = head;
      head->next->prev = 0;
      head = head->next;
      delete t;
    }
    _nItems--;
  } else
  {
    DEQUE_REMOVE;
  }
}

template <class T, class E>
void LinkedDequeImp<T, E>::removeTail ()
{
  if (_nItems > 0)
  {
    if (head == tail)
    {
      delete head;
      head = tail = 0;
    } else
    {
      E *t = tail;
      tail->prev->next = 0;
      tail = tail->prev;
      delete t;
    }
    _nItems--;
  } else
  {
    DEQUE_REMOVE;
  }
}

#define TypeDLinkedDeque(T)  LinkedDequeImp<T, DDoubleLinkItem<T> >
#define TypeIOLinkedDeque(T) LinkedDequeImp<T, IDoubleLinkItem<T, 1> >
#define TypeILinkedDeque(T)  LinkedDequeImp<T, IDoubleLinkItem<T, 0> >

#endif