linkedlist.h

用于词法分析的词法分析器

/*
  $Id: LinkedList.h,v 1.3 1997/02/02 01:31:03 matt Exp $

  Generic linked list.

  (c) Matt Phillips Feb 1995.
  */

#ifndef _LLIST_H
#define _LLIST_H

#include "List.h"

////////////////// LinkedListImp

template <class T, class E>
class LinkedListImp : public List<T>
{
public:

  typedef LinkedListImpIter<T, E> Iterator;

  LinkedListImp () : head (0) {}
  LinkedListImp (const LinkedListImp<T, E> &l);
  ~LinkedListImp () {clear ();}
   
  virtual void add (T &i) {head = new E (i, head); _nItems++;}

  virtual void clear ();

  virtual T &peekHead () const
  {CHECK (head, "peek on empty list"); return head->ref ();}

  void moveTo (LinkedListImp<T, E> &dest);

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

  friend Iterator;

  E *head;
};

template <class T, class E>
class LinkedListImpIter : public ListIter<T>
{
public:
   
  LinkedListImpIter (const LinkedListImp<T, E> &l) : list (l) {reset ();}
   
  virtual void reset () {i = list.head;}
  virtual operator int () const {return int (i);}
  virtual void operator ++ (int) {ITER_BOUND (i); i = i->next;}
  virtual T &ref () const {ITER_CURRENT (i); return i->ref ();}
  int hasNext () const {ITER_CURRENT (i); return int (i->next);}

  T &refNext () const
  {
    ITER_CURRENT (i);
    CHECK (i->next, "null refNext");
    return i->next->ref ();
  }
   
protected:

  void decNItems ()		// kludges for extended iter access
  {((LinkedListImp<T, E> &)list)._nItems--;} 
  void incNItems ()
  {((LinkedListImp<T, E> &)list)._nItems++;}
  void setHead (E *h)
  {((LinkedListImp<T, E> &)list).head = h;}

  E *i;
  const LinkedListImp<T, E> &list;
};

// in order copy constructor
template <class T, class E>
LinkedListImp<T, E>::LinkedListImp (const LinkedListImp<T, E> &l)
  : head (0)
{
  for (E *tail = 0, *i = l.head; i; i = i->next)
  {
    E *n = new E (*i);

    if (tail)
      tail->next = n;
    else
      head = n;
      
    tail = n;
  }

  _nItems = l._nItems;
}

template <class T, class E> void LinkedListImp<T, E>::clear ()
{
  E *i, *next;
   
  for (i = head; i; i = next)
  {
    next = i->next;
    delete i;
  }
  head = 0;
  _nItems = 0;
}

// move all items to <dest>
template <class T, class E>
void LinkedListImp<T, E>::moveTo (LinkedListImp<T, E> &dest)
{
  if (this == &dest)
    return;			// immediate return if dest = src

  if (_nItems > 0)
  {
    if (dest._nItems > 0)
    {
      E *head1, *head2, *e;

      // head1 = shortest list, head2 = longest list
      if (_nItems < dest._nItems)
	head1 = head, head2 = dest.head;
      else
	head2 = head, head1 = dest.head;
	 
      // find end of shortest (head1)
      for (e = head1; e->next; e = e->next);
	 
      e->next = head2;	// join lists
      dest.head = head1;
      dest._nItems += _nItems;
      _nItems = 0;
      head = 0;
    } else			// nothing in dest
    {
      dest.head = head;
      dest._nItems += _nItems;
    }
  }
}

#define TypeDLinkedList(T)  LinkedListImp<T, DLinkedItem<T> >
#define TypeILinkedList(T)  LinkedListImp<T, ILinkedItem<T, 0> >
#define TypeIOLinkedList(T) LinkedListImp<T, ILinkedItem<T, 1> >

#endif