circularqueue.h

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

/* $Id: CircularQueue.h,v 1.5 1997/05/19 02:16:25 matt Exp $

   Circular queue class.

   A simple-minded double-ended circular queue of objects stored as an
   expandable array.  Objects are bitwise copied and no ctor/dtor
   calls are made during creation/destruction/resize of array.

   NOTE: this is not part of the Container class tree because it
   provides no generic memory management and only allows the direct
   storage model.  However, it does implement most of the standard
   Container interface for ease of use.

   (c) 1996 Matt Phillips. */

#ifndef _CIRC_QUEUE
#define _CIRC_QUEUE

template <class T>
class CircularQueue
{
public:

  enum {InitSize = 16};		// initial # of elements in the queue
  enum {ResizeFactor = 2};	// queue size expands in multiples of this

  CircularQueue ();
  CircularQueue (const CircularQueue<T> &q);
  ~CircularQueue ();

  T *pushHead ();
  int popHead ();
  T *peekHead () const {return isEmpty () ? 0 : (T *)queue + head;}

  T *pushTail ();
  int popTail ();
  T *peekTail () const {return isEmpty () ? 0 : (T *)queue + tail;}

  void popHead (int n);
  void popTail (int n);

  void clear () {head = tail = size = 0;}

  int nItems () const {return size;}
  int isFull () const {return size == queueSize;}
  int isEmpty () const {return size == 0;}

  void assign (const CircularQueue<T> &q);

protected:

  T *queue;
  int queueSize;
  int head, tail;
  int size;

  void expand ();
};

template <class T>
CircularQueue<T>::CircularQueue ()
{
  queue = 0;
  size = queueSize = 0;
  head = tail = 0;
}

template <class T>
CircularQueue<T>::CircularQueue (const CircularQueue<T> &q)
{
  queue = 0;
  assign (q);
}

template <class T>
CircularQueue<T>::~CircularQueue ()
{
  delete [] queue;
}

template <class T>
T *CircularQueue<T>::pushHead ()
{
  if (isFull ())
    expand ();

  if (size != 0)
    head = (head + 1) % queueSize;

  size++;

  return queue + head;
}

template <class T>
int CircularQueue<T>::popHead ()
{
  if (isEmpty ())
    return 0;

  if (head == 0)
    head = queueSize - 1;
  else
    head--;

  size--;

  return 1;
}

template <class T>
T *CircularQueue<T>::pushTail ()
{
  if (isFull ())
    expand ();

  if (size != 0)
  {
    if (tail == 0)
      tail = queueSize - 1;
    else
      tail--;
  }

  size++;

  return queue + tail;
}

template <class T>
int CircularQueue<T>::popTail ()
{
  if (isEmpty ())
    return 0;

  if (size > 1)
    tail = (tail + 1) % queueSize;

  size--;

  return 1;
}

template <class T>
void CircularQueue<T>::popHead (int n)
{
  if (n >= size)
  {
    clear ();
  } else if (n > 0)
  {
    head -= n;

    if (head < 0)
      head += queueSize;

    size -= n;
  }
}

template <class T>
void CircularQueue<T>::popTail (int n)
{
  if (n >= size)
  {
    clear ();
  } else if (n > 0)
  {
    tail = (tail + n) % queueSize;
    size -= n;
  }
}

template <class T>
void CircularQueue<T>::assign (const CircularQueue<T> &q)
{
  size = q.size;
  queueSize = q.queueSize;
  head = q.head;
  tail = q.tail;
  delete queue;

  if (q.queue)
  {
    queue = new T [queueSize];
    memcpy (queue, q.queue, queueSize * sizeof (T));
  }
}

template <class T>
void CircularQueue<T>::expand ()
{
  int newQueueSize = (queueSize == 0) ? InitSize : queueSize * ResizeFactor;
  T *newQueue = new T [newQueueSize];

  if (tail <= head)
    memcpy (newQueue, queue, queueSize * sizeof (T));
  else
  {
    // the items in the queue wrap over the right edge.  we need to
    // reassemble the two pieces into one single piece which starts
    // from offset 0 in the new queue.
    int tailItems = queueSize - tail; // the number of items in the tail

    memcpy (newQueue, queue + tail,  tailItems * sizeof (T));
    memcpy (newQueue + tailItems, queue, (head + 1) * sizeof (T));

    tail = 0;
    head += tailItems;
  }

  delete queue;
  queue = newQueue;
  queueSize = newQueueSize;
}

#endif