// Resizable Circular Queues in C++ using unique_ptr

#include<iostream>
#include<memory>
#include<string>
using namespace std;

// macro from Stack Overflow (Konrad Rudolph):
#ifndef NDEBUG
#   define ASSERT(condition, message) \
    do { \
        if (! (condition)) { \
	  std::cerr << "Assertion `" #condition "` failed in " << __FILE__ \
                      << " line " << __LINE__ << ": " << message << std::endl; \
	  std::terminate();						\
        } \
    } while (false)
#else
#   define ASSERT(condition, message) do { } while (false)
#endif
// dummy while loop allows ; to be placed at end of macro

typedef unsigned int uint;  // just for convenience


template<typename T>
class CircQueue
{
protected:
  unique_ptr<T[]> Q; // dynamically allocated array,
  uint capacity;     // unique_ptr still allows [] notation
  unsigned int size;
  uint front; // real index of first element
  uint end()   // one spot past last index, next available
  { return (front+size) % capacity; }
  uint right(uint i) { return (i+1)%capacity; } // real index to the right
  uint left(uint i) { return (i+capacity-1) % capacity; } // and to the left
public:
  uint length() { return size; }
  uint current_capacity() { return capacity; }
  CircQueue() // constructor creates Q with capacity one
  {
    capacity = 1;
    Q = unique_ptr<T[]>(new T[1]);
    size = front=0;
  }
  CircQueue(uint cap) // alt constructor
  {
    if (cap<1) cap = 1;
    capacity=cap;
    size=front=0;
    Q = unique_ptr<T[]>(new T[cap]);
  }
  // only the default destructor is needed because of unique_ptr
  
  uint resize() // double capacity of Queue, returns new capacity
  {
    unique_ptr<T[]> Q2(new T[capacity*2]);
    // copy info over...
    for(uint i=0;i<size;i++) Q2[i] = Q[(front+i)%capacity];
    front = 0; // but size stays the same
    capacity *= 2;
    Q = move(Q2);    // take over
    //cout << "resize returning " << capacity << endl; //trace
    return capacity;
  }// resize

  ////////////////  Common Operations, all takes O(1) time

  void push(T x) // add to front of queue
  {
    if (size>=capacity) resize(); // resize on demand.
    if (size>0) front = left(front);
    Q[front] = x;
    size++;
  }
  T pop() // remove and return from front
  {
    ASSERT(size>0, "buffer underflow");
    T answer = Q[front];
    Q[front] = {};  // {} is default value of T  (C++11 and later)
    front = right(front);
    size--;
    return answer;
  }
  void enqueue(T x) // add to end of queue
  {
    if (size>=capacity) resize();
    Q[end()] = x;
    size++;
  }
  T dequeue() // delete from end, also O(1)
  {
    ASSERT(size>0, "buffer underflow");
    T answer = Q[(front+size-1)%capacity];
    // but answer still in Q. do we leave it there? obviously not!
    Q[(front+size-1)%capacity] = {}; // valid only since C++ 11
    size--;
    return answer;
  }

  ///////////////
  T geti(uint i) // get ith virtual-index value from front (0=front)
  {
    ASSERT(i<size, "invalid index for CircQueue.get");
    return Q[ (front+i)%capacity ];
  }
  void seti(uint i, T x)// sets ith virtual index value to x
  {
    ASSERT(i<size, "invalid index for CircQueue.get");
    Q[ (front+i)%capacity ] = x;
  } 
};  // class CircQueue


int main()
{
  CircQueue<int> bigQ(2); // note: not a pointer
  for(int i = 0;i<1000;i++)
    { bigQ.enqueue(2*i);
      bigQ.push(2*i+1);
    }

  /*
  int sum = 0; 
  bigQ.foreach([sum](int x) mutable {sum+=x;} );
  cout << "sum of Q is "<< sum << endl;
  */
  cout << bigQ.pop() << " and " << bigQ.dequeue() << endl;
  cout << bigQ.pop() << " and " << bigQ.dequeue() << endl;
  cout << bigQ.pop() << " and " << bigQ.dequeue() << endl;
  cout << bigQ.pop() << " and " << bigQ.dequeue() << endl;  
  cout << bigQ.length() << endl;

  return 0;
}//main