#include <stdexcept>
#include <iostream>

using namespace std;

template <typename T,int N>
class Queue {
  private:
    T elems[N+1];
    int tail,head;
  public:
    Queue();
    ~Queue() {cout<<"discarding Queue of "<<N<<" "<<typeid(T).name()<<endl;}
    bool empty() const {
      return tail==head;
      }
    void enqueue(T const&);
    T dequeue();
  };

template <typename T,int N>
Queue<T,N>::Queue(): tail(0),head(0)
{
  cout<<"constructing Queue of "<<N<<" "<<typeid(T).name()<<endl;
}

template <typename T,int N>
void Queue<T,N>::enqueue(T const& x)
{
  elems[tail++]=x;
  if (tail==N+1)
    tail=0;
  if (empty())
    throw std::out_of_range("Queue<>::enqueue(): queue is full");
}

template <typename T,int N>
T Queue<T,N>::dequeue()
{
  T temp;

  if (empty())
    throw std::out_of_range("Queue<>::dequeue(): queue is empty");
  temp=elems[head++];
  if (head==N+1)
    head=0;
  return temp;
}

Queue<int,10> TenInts;
Queue<double,100> HundredDoubles;

class Person {
  public:
    string name;
    int age;
    float gpa;
  };

Queue<Person,50> FiftyPersons;

Queue<void*,10> TenVoidPtrs;

int main()
{
  int i,*k;
  Person p,*q;

  for (i=0;i<10;i++)
    TenInts.enqueue(i);
  for (i=0;i<10;i++)
    if (i!=TenInts.dequeue())
      throw std::out_of_range("Queue<>::dequeue(): incorrect value");
  if (TenInts.empty())
    cout<<"TenInts works"<<endl;

  for (i=0;i<100;i++)
    HundredDoubles.enqueue(i);
  for (i=0;i<100;i++)
    if (i!=HundredDoubles.dequeue())
      throw std::out_of_range("Queue<>::dequeue(): incorrect value");
  if (HundredDoubles.empty())
    cout<<"HundredDoubles works"<<endl;

  p.name="Joe";
  p.gpa=3.3;
  for (i=0;i<50;i++)
  {
    p.age=i;
    FiftyPersons.enqueue(p);
  }
  for (i=0;i<50;i++)
  {
    p=FiftyPersons.dequeue();
    if (p.name!="Joe" || p.age!=i)
      throw std::out_of_range("Queue<>::dequeue(): incorrect value");
  }
  if (FiftyPersons.empty())
    cout<<"FiftyPersons works"<<endl;

  for (i=0;i<5;i++)
  {
    k=new int;
    (*k)=i;
    TenVoidPtrs.enqueue((void*) k);
  }

  for (i=0;i<5;i++)
  {
    q=new Person;
    q->name="Alice";
    q->gpa=i;
    q->age=i;
    TenVoidPtrs.enqueue((void*) q);
  }

  for (i=0;i<5;i++) {
    k=(int*)TenVoidPtrs.dequeue();
    if (*k!=i)
      throw std::out_of_range("Queue<>::dequeue(): incorrect value");
    else
      delete k;
    }

  for (i=0;i<5;i++)
  {
    q=(Person*)TenVoidPtrs.dequeue();
    if (q->name!="Alice" || q->gpa!=i || q->gpa!=i)
      throw std::out_of_range("Queue<>::dequeue(): incorrect value");
    delete q;
  }

  if (TenVoidPtrs.empty())
    cout<<"TenVoidPtrs works"<<endl;
}