///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//  Copyright (C) 1995-1998 by the Board of Trustees of Leland Stanford      //
//  Junior University.  See LICENSE for details.                             //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#ifndef _queue_h_
#define _queue_h_

#include "misc.h"

template <class _Data> class Queue_Link;
template <class _Data> class Queue;

template <class _Data>
class Queue_Link {
private:
  _Data _data;
  Queue_Link *_next;

public:
  Queue_Link(_Data d) : _data(d), _next(NULL) {}
  _Data Data() { return _data; }
  Queue_Link* &Next() { return _next; }
};


template <class _Data>
class Queue {
protected:
  Queue_Link<_Data> *_head;
  Queue_Link<_Data> **_tail;

public:
  Queue() : _head(NULL), _tail(&_head) {}
  void Destroy();
  void Insert(_Data d);
  _Data GetNext();
  Bool Empty() { return _head == NULL; }
};


template <class _Data>
void Queue<_Data>::Insert(_Data d)
{
  *_tail = new Queue_Link<_Data>(d);
  _tail = &(*_tail)->Next();
}


template <class _Data>
void Queue<_Data>::Destroy()
{
  Queue_Link<_Data> *tmp = _head;
  while (tmp) {
    _head = tmp->Next();
    delete tmp;
    tmp = _head;
  }
  _tail = &_head;
}


template <class _Data>
_Data Queue<_Data>::GetNext()
{
  assert_msg(_head != NULL, ("GetNext called on empty queue"));
  _Data result = _head->Data();
  Queue_Link<_Data> *tmp = _head;
  _head = _head->Next();
  delete tmp;
  if (_head == NULL)
    _tail = &_head;
  return result;
}


#endif