sortedlinkedlist.h

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

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

  Sorted linked lists.
  (Sorted derivative of the LinkedListImp class)

  (c) Feb 1995 Matt Phillips.
  */

#ifndef _SLLIST_H
#define _SLLIST_H

#include "LinkedList.h"

//////////////////// SortedLinkedListImp

// class T must have the < and <= operators defined
template <class T, class E>
class SortedLinkedListImp : public LinkedListImp<T, E>
{
public:

  SortedLinkedListImp () {}
  SortedLinkedListImp (const SortedLinkedListImp<T, E> &l) :
    LinkedListImp<T, E> (l) {}

  virtual const char *name () const {return "SortedList";}

  int operator == (const SortedLinkedListImp<T, E> &l) const;

  virtual void add (T &i);
  void moveTo (SortedLinkedListImp<T, E> &dest);
  void copyTo (SortedLinkedListImp<T, E> &dest) const;

  int isSorted () const;	// diagnostic
};

template <class T, class E>
void SortedLinkedListImp<T, E>::add (T &i)
{
  E *prev, *c, *newElem = new E (i, 0);

  // search list
  for (prev = 0, c = head; c && c->ref () < i; prev = c, c = c->next);
  
  if (prev)
  {
    newElem->next = prev->next;
    prev->next = newElem;
  } else
  {
    newElem->next = head;
    head = newElem;
  }

  _nItems++;
}

template <class T, class E>
int SortedLinkedListImp<T, E>::
operator == (const SortedLinkedListImp<T, E> &l) const
{
  if (_nItems == l._nItems)
  {
    E *left, *right;

    for (left = head, right = l.head;
	 left;
	 left = left->next, right = right->next)
    {
      CHECK (right, "list is corrupt");
      if (!(left->ref () == right->ref ()))
	return 0;
    }
      
    CHECK (!left && !right, "list is corrupt");
      
    return 1;
  } else
    return 0;
}

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

  for (E *left = head, *right = dest.head, *prev = 0;
       left || right; /* no increment */ )
  {
    if (!right || (left && left->ref () <= right->ref ()))
    {
      if (prev)
	prev->next = left;
      else
	dest.head = left;

      prev = left;
      left = left->next;
    } else if (!left || (right && right->ref () <= left->ref ()))
    {
      if (prev)
	prev->next = right;
      else
	dest.head = right;

      prev = right;
      right = right->next;
    }
  }

  dest._nItems += _nItems;  
  _nItems = 0;			// clear list
  head = 0;
}

// copy all items to <dest>
template <class T, class E>
void SortedLinkedListImp<T, E>::copyTo (SortedLinkedListImp<T, E> &dest) const
{
  CHECK (this != &dest, "copyTo cannot handle dest == src");

  for (E *left = head, *right = dest.head, *prev = 0;
       left || right; /* no increment */ )
  {
    if (!right || (left && left->ref () <= right->ref ()))
    {
      E *e = new E (*left);

      if (prev)
	prev->next = e;
      else
	dest.head = e;

      prev = e;
      left = left->next;
    } else if (!left || (right && right->ref () <= left->ref ()))
    {
      if (prev)
	prev->next = right;
      else
	dest.head = right;

      prev = right;
      right = right->next;
    }
  }

  dest._nItems += _nItems;  
}

template <class T, class E>
int SortedLinkedListImp<T, E>::isSorted () const
{
  for (E *i = head, *prev = 0; i; prev = i, i = i->next)
  {
    if (prev && !(prev->ref () <= i->ref ()))
      return 0;
  }

  return 1;
}

#define TypeDSortedLinkedList(T)  SortedLinkedListImp<T, DLinkedItem<T> >
#define TypeISortedLinkedList(T)  SortedLinkedListImp<T, ILinkedItem<T, 0> >
#define TypeIOSortedLinkedList(T) SortedLinkedListImp<T, ILinkedItem<T, 1> >

#endif